Tìm hàng có số 1s tối đa bằng C ++

Trong bài toán này, chúng ta được cung cấp một ma trận nhị phân trong đó các phần tử của mỗi hàng được sắp xếp. Nhiệm vụ của chúng tôi là tìm hàng có số 1s tối đa .

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

mat[][] = {{ 0 1 1 1}
   {1 1 1 1}
   {0 0 0 1}
   {0 0 1 1}}

Đầu ra

1

Giải thích

The count of 1’s in each row of the matrix :
Row 0 : 3
Row 1 : 4
Row 2 : 1
Row 3 : 2

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là tìm hàng có chỉ số nhỏ nhất trong số 1 đầu tiên.

Một cách tiếp cận là sử dụng duyệt hàng khôn ngoan để tìm chỉ số của 1 đầu tiên sẽ trả về số lượng tối đa là 1 trong hàng. Và sau đó chúng tôi sẽ trả về hàng có số lượng tối đa 1.

Một cách tiếp cận khác là sử dụng tìm kiếm nhị phân để tìm sự xuất hiện của 1 đầu tiên trong mỗi hàng. Sau đó, chúng tôi sẽ trả về giá trị với giá trị lớn nhất là 1.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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 max1RowIndex = 0, max = -1;
   for (int i = 0; i < R; i++){
      int first1Index = findFirst1BinSearch(mat[i], 0, C-1);
      if (first1Index != -1 && C-first1Index > max){
         max = C - first1Index;
         max1RowIndex = i;
      }
   }
   return max1RowIndex;
}
int main(){
   bool mat[R][C] = { {0, 1, 1, 1},
   {1, 1, 1, 1},
   {0, 0, 1, 1},
   {0, 0, 0, 1}};
   cout<<"The row with maximum number of 1's in the matrix is "<<findMaxOneRow(mat);
   return 0;
}

Đầu ra

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