# 查找最大数量为 1 的行 > 原文： [https://www.geeksforgeeks.org/find-the-row-with-maximum-number-1s/](https://www.geeksforgeeks.org/find-the-row-with-maximum-number-1s/) 给定一个布尔 2D 数组，其中对每一行进行排序。 查找最大为 1s 的行。 **示例**： ``` Input matrix 0 1 1 1 0 0 1 1 1 1 1 1 // this row has maximum 1s 0 0 0 0 Output: 2 ``` **一种简单的方法**是对矩阵进行逐行遍历，计算每行中 1 的数量，然后将其与最大值进行比较。 最后，返回最大为 1s 的行的索引。 此方法的时间复杂度为 O（m * n），其中 m 是矩阵中的行数，n 是矩阵中的列数。 我们可以做得更好。 由于每一行都已排序，因此我们可以**使用二分搜索**在每一行中计数 1。 我们在每一行中找到 1 的第一个实例的索引。 1 的计数等于列总数减去前 1 的索引。 请参见以下代码，以实现上述方法。 ## C++ ```cpp // CPP program to find the row  // with maximum number of 1s  #include <bits/stdc++.h> using namespace std; #define R 4  #define C 4  // Function to find the index of first index  // of 1 in a boolean array arr[]  int first(bool arr[], int low, int high)  {      if(high >= low)      {          // Get the middle index          int mid = low + (high - low)/2;          // Check if the element at middle index is first 1          if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)              return mid;          // If the element is 0, recur for right side          else if (arr[mid] == 0)              return first(arr, (mid + 1), high);          // If element is not first 1, recur for left side          else             return first(arr, low, (mid -1));      }      return -1;  }  // Function that returns index of row  // with maximum number of 1s.  int rowWithMax1s(bool mat[R][C])  {      // Initialize max values      int max_row_index = 0, max = -1;      // Traverse for each row and count number of 1s      // by finding the index of first 1      int i, index;      for (i = 0; i < R; i++)      {          index = first (mat[i], 0, C-1);          if (index != -1 && C-index > max)          {              max = C - index;              max_row_index = i;          }      }      return max_row_index;  }  // Driver Code  int main()  {      bool mat[R][C] = { {0, 0, 0, 1},                      {0, 1, 1, 1},                      {1, 1, 1, 1},                      {0, 0, 0, 0}};      cout << "Index of row with maximum 1s is " << rowWithMax1s(mat);      return 0;  }  // This is code is contributed by rathbhupendra ```