C++で最大数が1のバイナリ行列の行番号を検索します

この問題では、各行がソートされたバイナリ行列が与えられます。私たちのタスクは、最大数が1のバイナリ行列の行番号を見つけることです。

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

入力

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

出力

1

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

この問題の簡単な解決策は、各行の1の総数を数えることです。次に、最大1カウントの行番号を返します。

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

例

#include <iostream>
using namespace std;
#define R 4
#define C 4
int findMax1Row(bool mat[R][C]) {
   int max1Row = 0, max1Count = -1;
   int i, index;
   for (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;
}

出力

最大数が1の行の数は1です。この問題のより良い解決策は、各行で2分探索を使用して、行内で最初に出現する1を見つけることです。行の番号1は、行サイズ（最初の1のインデックス）を使用して見つけることができます。これを使用して、各行の1の数を見つけ、最大数1の行を返すことができます

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

例

#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;
   int i, index;
   for (i = 0; i < R; i++) {
      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;
}

出力

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

上記のアプローチに追加された最適化は、最初の1のインデックスを使用して、現在の行に前の行よりも1が多いかどうかをチェックできます。1が多い場合は、バイナリ検索を実行しますが、0から最後の行の最初の1のインデックスまでです。

これにより、現在の1よりも1が少ない行の1の数を計算するオーバーヘッドを節約できます。

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

例

#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 i, index;
   int max1Row = 0;
   int max1Count = binarySearch1Row(mat[0], 0, C - 1);
   for (i = 1; i < R; i++){
      if (max1Count != -1 && mat[i][C - max1Count - 1] == 1) {
         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;
}

出力

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