查找最大數為 1 的二進制矩陣的行號 · GeeksForGeeks 中文系列教程

# 查找最大數為 1 的二進制矩陣的行號 > 原文： [https://www.geeksforgeeks.org/find-row-number-binary-matrix-maximum-number-1s/](https://www.geeksforgeeks.org/find-row-number-binary-matrix-maximum-number-1s/) 給定 n * n 階的二進制矩陣（僅包含 0 和 1）。所有行均已排序，我們需要找到最大為 1s 的行號。還要在該行中找到數字 1。注意：如果是平局，則打印較小的行號。 **示例**： ``` Input : mat[3][3] = {0, 0, 1, 0, 1, 1, 0, 0, 0} Output : Row number = 2, MaxCount = 2 Input : mat[3][3] = {1, 1, 1, 1, 1, 1, 0, 0, 0} Output : Row number = 1, MaxCount = 3 ``` **基本方法**：遍歷整個矩陣，并為每行找到 1 的數目，并在所有行中不斷更新最大數目為 1 的行號。此方法將導致 O（n ^ 2）時間復雜度。 **更好的方法**：如果我們嘗試應用二分搜索來查找每行中第一個 1 的位置，并且隨著對每一行進行排序就可以從每行中找到 1 的數目，那么我們可以做得更好訂購。這將導致 O（nlogn）時間復雜度。 **有效方法**：從索引（1，n）的左上角開始，嘗試向左移動直到到達該行（第 j 列）的最后 1 個，現在如果我們向左移動到該行，我們將找到 0，因此切換到同一列的正下方。現在，如果第 j 個元素（如果 1）嘗試向左移動，則您的位置將再次位于第二行（2，j），直到找到最后 1 個；否則，如果第 j 個元素為 0，則在第二行中轉到下一行。因此，最后要說的是，如果您位于第 ith 行和第 j 列中的任何一個，即該行右邊的最后 1 個索引，則遞增 i。因此，現在如果 Aij = 0 再次增加 i，否則繼續減少 j，直到在該特定行中找到最后 1 個為止。示例圖： ![](https://img.kancloud.cn/5d/ac/5dace99475cdd853bc4852b9ede525bd_303x319.png) **算法**： ``` for (int i=0, j=n-1; i<n;i++) { // find left most position of 1 in a row // find 1st zero in a row while (arr[i][j]==1) { row = i; j--; } } cout << "Row number =" << row+1; cout << "MaxCount =" << n-j; ``` ## C++ ```cpp // CPP program to find row with maximum 1 // in row sorted binary matrix #include<bits/stdc++.h> #define N 4 using namespace std; // function for finding row with maximum 1 void findMax (int arr[][N]) { ????int row = 0, i, j; ????for (i=0, j=N-1; i<N;i++) ????{ ????????// find left most position of 1 in a row ????????// find 1st zero in a row ????????while (arr[i][j] == 1 && j >= 0)? ????????{ ????????????row = i; ????????????j--; ????????} ????} ????cout << "Row number = " << row+1; ????cout << ", MaxCount = " << N-1-j; } // driver program int main() { ????int arr[N][N] = {0, 0, 0, 1, ?????????????????????0, 0, 0, 1, ?????????????????????0, 0, 0, 0, ?????????????????????0, 1, 1, 1}; ????findMax(arr); ????return 0; } ``` ## Java ```java // Java program to find row with maximum 1 // in row sorted binary matrix class GFG { ????static final int N = 4; ????// function for finding row with maximum 1 ????static void findMax(int arr[][]) { ????????int row = 0, i, j; ????????for (i = 0, j = N - 1; i < N; i++) { ????????????// find left most position of 1 in ????????????// a row find 1st zero in a row ????????????while (j >= 0 && arr[i][j] == 1) { ????????????????row = i; ????????????????j--; ????????????} ????????} ????????System.out.print("Row number = "? ????????????????????????????????+ (row + 1)); ????????System.out.print(", MaxCount = "? ???????????????????????????????+ (N - 1 - j)); ????} ????// Driver code ????public static void main(String[] args) { ????????int arr[][] = {{0, 0, 0, 1},? ???????????????????????{0, 0, 0, 1},? ???????????????????????{0, 0, 0, 0},? ???????????????????????{0, 1, 1, 1}}; ????????findMax(arr); ????} } // This code is contributed by Anant Agarwal. ``` ## Python3 ```py # python program to find row with # maximum 1 in row sorted binary # matrix N = 4 # function for finding row with # maximum 1 def findMax (arr): ????row = 0 ????j = N - 1 ????for i in range(0, N): ????????# find left most position ????????# of 1 in a row find 1st ????????# zero in a row ????????while (arr[i][j] == 1? ?????????????????????and j >= 0): ????????????row = i ????????????j -= 1 ????print("Row number = " , row + 1, ?????????", MaxCount = ", N - 1 - j) # driver program arr = [ [0, 0, 0, 1], ????????[0, 0, 0, 1], ????????[0, 0, 0, 0], ????????[0, 1, 1, 1] ] findMax(arr) # This code is contributed by Sam007 ``` ## C# ```cs // C# program to find row with maximum // 1 in row sorted binary matrix using System; class GFG { ????static int N = 4; ????// function for finding row with maximum 1 ????static void findMax(int [,]arr) ????{ ????????int row = 0, i, j; ????????for (i = 0, j = N - 1; i < N; i++) { ????????????// find left most position of 1 in ????????????// a row find 1st zero in a row ????????????while (arr[i,j] == 1 && j >= 0)? ????????????{ ????????????????row = i; ????????????????j--; ????????????} ????????} ????????Console.Write("Row number = " + (row + 1)); ????????Console.Write(", MaxCount = " + (N - 1 - j)); ????} ????// Driver code ????public static void Main()? ????{ ????????int [,]arr = {{0, 0, 0, 1},? ??????????????????????{0, 0, 0, 1},? ??????????????????????{0, 0, 0, 0},? ??????????????????????{0, 1, 1, 1}}; ????????findMax(arr); ????} } // This code is contributed by nitin mittal ``` ## PHP ```php <?php // PHP program to find? // row with maximum 1 // in row sorted? // binary matrix $N = 4; // function for finding // row with maximum 1 function findMax ($arr) { ????global $N; ????$row = 0; $i;? ????$j=$N - 1; ????for ($i = 0; $i < $N; $i++) ????{ ????????// find left most position ????????// of 1 in a row find 1st ????????// zero in a row ????????while ($arr[$i][$j] == 1 &&? ???????????????????????????$j >= 0)? ????????{ ????????????$row = $i; ????????????$j--; ????????} ????} ????echo "Row number = " , $row + 1; ????echo ", MaxCount = " , $N - 1 - $j; } ????// Driver Code ????$arr = array(array(0, 0, 0, 1), ?????????????????array(0, 0, 0, 1), ?????????????????array(0, 0, 0, 0), ?????????????????array(0, 1, 1, 1)); ????findMax($arr); // This code is contributed by vt_m. ?> ``` Output: ``` Row number = 4, MaxCount = 3 ``` 本文由 [**Shivam Pradhan（anuj_charm）**](http://www.facebook.com/ma5ter6it) 提供。如果您喜歡 GeeksforGeeks 并希望做出貢獻，則還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。