在 C++ 中查找最大数为 1 的二进制矩阵的行号

2023-06-16 12:16:04 78

在这个问题中，我们给出了一个二进制矩阵，其中每一行都被排序。我们的任务是找到最大数量为1的二进制矩阵的行号。

让我们举个例子来理解这个问题，

输入

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

输出结果

解决方法

该问题的一个简单解决方案是计算每行中1的总数。然后返回最大1个计数的行号。

程序来说明我们的解决方案的工作，

示例

#include 
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 "<输出结果
最大1的行数是1一个更好的解决方案是对每一行使用二分搜索来找到该行中第一次出现的1。可以使用行大小-第一个1的索引找到行中的数字1。使用它，我们可以找到每行中1的数量，然后返回最大数量为1的行
程序来说明我们的解决方案的工作，
示例
#include 
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 "<输出结果The number of row with maximum number of 1's is 1
添加到上述方法的优化可以使用第一个1的索引检查当前行是否比前一行有更多的1。如果它有更多的1，则执行二分查找，但从0到最后一行的第一个1的索引。
这将节省计算比当前1少的1的行数的开销。
程序来说明我们的解决方案的工作，
示例
#include 
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 "<输出结果The number of row with maximum number of 1's is 1

在 C++ 中查找最大数为 1 的二进制矩阵的行号

输入

解决方法

示例

示例

示例

热门推荐

随机推荐