查找最大數量為 1 的行 · GeeksForGeeks 中文系列教程

# 查找最大數量為 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 ```