C ++を使用して、最大数が1の行を検索します

この問題では、各行の要素が並べ替えられたバイナリ行列が与えられます。私たちのタスクは、最大数が1の行を見つけることです。 。

問題を理解するために例を見てみましょう

入力

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

出力

1

説明

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

ソリューションアプローチ

この問題の簡単な解決策は、最初の1のインデックスが最小の行を見つけることです。

1つのアプローチは、行ごとのトラバーサルを使用して、行の最大カウント1を返す最初の1のインデックスを見つけることです。次に、最大1カウントの行を返します。

別のアプローチは、二分探索を使用することです。 各行の最初の1の出現を検索します。次に、最大1の値を返します。

例

ソリューションの動作を説明するプログラム

#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;
}

出力

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