Tìm hàng có nhiều số 1 nhất trong ma trận nhị phân bằng C++

Mô tả bài toán

Cho ma trận nhị phân các hàng đã sắp xếp (0 trước, 1 sau). Tìm chỉ số hàng chứa nhiều số 1 nhất.

Ví dụ

mat = {{0,1,1,1},{1,1,1,1},{0,0,1,1},{0,0,0,1}} → Output: 1 (hàng 1 có 4 số 1).

Giải thuật

• Duyệt từng hàng, dùng tìm kiếm nhị phân tìm chỉ số số 1 đầu tiên.
• Số 1 trong hàng = C - firstOneIndex. Cập nhật hàng tối đa.

Mã nguồn C++

#include <iostream>
using namespace std;
#define R 4
#define C 4

int findFirst1BinSearch(bool arr[], int low, int high) {
    if (high >= low) {
        int mid = low + (high-low)/2;
        if ((mid==0 || arr[mid-1]==0) && arr[mid]==1) return mid;
        else if (arr[mid]==0) return findFirst1BinSearch(arr, mid+1, high);
        else return findFirst1BinSearch(arr, low, mid-1);
    }
    return -1;
}

int findMaxOneRow(bool mat[R][C]) {
    int maxRow = 0, maxOnes = -1;
    for (int i=0; i maxOnes) { maxOnes = C-idx; maxRow = i; }
    }
    return maxRow;
}

int main() {
    bool mat[R][C] = {{0,1,1,1},{1,1,1,1},{0,0,1,1},{0,0,0,1}};
    cout << "Row with maximum 1s is " << findMaxOneRow(mat);
    return 0;
}

Đầu ra

The row with maximum number of 1's in the matrix is 1