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

Trong bài toán này, cho ma trận nhị phân các hàng đã sắp xếp. Nhiệm vụ là tìm số hàng có nhiều số 1 nhất.

Ví dụ minh họa:

Đầu vào

binMat[][] = { {1, 1, 1, 1}, {0, 0, 0, 0}, {0, 0, 0, 1}, {0, 0, 1, 1} }

Đầu ra

1

Phương pháp giải

Cách 1: Đếm số 1 từng hàng, trả về hàng max count. O(R*C).

Chương trình (Cách 1):

Ví dụ

#include <iostream> 
using namespace std; 

#define R 4 
#define C 4 

int findMax1Row(bool mat[R][C]) { 
    int max1Row = 0, max1Count = -1; 
    for (int i = 0; i < R; i++) { 
        int oneCount = 0; 
        for(int j = 0; j < C; j++) if(mat[i][j]) oneCount++; 
        if(oneCount > max1Count){ max1Count = oneCount; max1Row = i; } 
    } 
    return (max1Row + 1); 
} 

int main() { 
    bool mat[R][C] = { {0, 1, 1, 1}, {0, 0, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0} }; 
    cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat); 
    return 0; 
}

Kết quả

The number of row with maximum number of 1's is 1

Cách 2: Dùng tìm kiếm nhị phân (binary search) trên mỗi hàng tìm vị trí 1 đầu tiên. Số 1 = C - index. O(R log C).

Chương trình (Cách 2):

Ví dụ

#include <iostream> 
using namespace std; 

#define R 4 
#define C 4 

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

int findMax1Row(bool mat[R][C]) { 
    int max1Row = 0, max1Count = -1; 
    for (int i = 0; i < R; i++) { 
        int index = binarySearch1Row(mat[i], 0, C-1); 
        if (index != -1 && (C-index) > max1Count) { 
            max1Count = C - index; max1Row = i; 
        } 
    } 
    return (max1Row + 1); 
} 

int main() { 
    bool mat[R][C] = { {0, 1, 1, 1}, {0, 0, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0} }; 
    cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat); 
    return 0; 
}

Kết quả

The number of row with maximum number of 1's is 1

Cách 3 (Tối ưu): Nếu hàng hiện tại có 1 nhiều hơn hàng trước (kiểm tra mat[i][C-max1Count-1] == 1), chỉ binary search từ 0 đến C-max1Count. Tiết kiệm thời gian.

Chương trình (Cách 3):

Ví dụ

#include <iostream> 
using namespace std; 

#define R 4 
#define C 4 

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

int findMax1Row(bool mat[R][C]) { 
    int max1Row = 0; 
    int max1Count = binarySearch1Row(mat[0], 0, C - 1); 
    for (int i = 1; i < R; i++){ 
        if (max1Count != -1 && mat[i][C - max1Count - 1] == 1) { 
            int index = binarySearch1Row(mat[i], 0, C - max1Count); 
            if (index != -1 && C - index > max1Count) { 
                max1Count = C - index; max1Row = i; 
            } 
        } else max1Count = binarySearch1Row(mat[i], 0, C - 1); 
    } 
    return (max1Row + 1); 
} 

int main() { 
    bool mat[R][C] = { {0, 1, 1, 1}, {0, 0, 0, 1}, {0, 0, 1, 1}, {0, 0, 0, 0} }; 
    cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat); 
    return 0; 
}

Kết quả

The number of row with maximum number of 1's is 1