# 在按行和按列排序的矩陣中計數零 > 原文： [https://www.geeksforgeeks.org/count-zeros-in-a-row-wise-and-column-wise-sorted-matrix/](https://www.geeksforgeeks.org/count-zeros-in-a-row-wise-and-column-wise-sorted-matrix/) 給定一個 N x N 的二進制矩陣（矩陣中的元素可以為 1 或 0），其中矩陣的每一行和每一列都按升序排序，其中計數為 0。 預期時間復雜度為`O(n)`。 **示例**： ``` Input: [0, 0, 0, 0, 1] [0, 0, 0, 1, 1] [0, 1, 1, 1, 1] [1, 1, 1, 1, 1] [1, 1, 1, 1, 1] Output: 8 Input: [0, 0] [0, 0] Output: 4 Input: [1, 1, 1, 1] [1, 1, 1, 1] [1, 1, 1, 1] [1, 1, 1, 1] Output: 0 ``` 這個想法很簡單。 我們從矩陣的左下角開始，然后重復以下步驟，直到找到矩陣的頂部或右側。 1.遞減行索引，直到找到 0。 2.在當前列中添加 0 數，即當前行索引+ 1，然后向右移至下一列（將 col index 遞增 1）。 由于矩陣是按行和按列排序的，因此上述邏輯將起作用。 該邏輯也適用于任何包含非負整數的矩陣。 下面是上述想法的實現： ## C++ ```cpp // C++ program to count number of 0s in the given // row-wise and column-wise sorted binary matrix. #include <iostream> using namespace std; // define size of square matrix #define N 5 // Function to count number of 0s in the given // row-wise and column-wise sorted binary matrix. int countZeroes(int mat[N][N]) { ????// start from bottom-left corner of the matrix ????int row = N - 1, col = 0; ????// stores number of zeroes in the matrix ????int count = 0; ????while (col < N) ????{ ????????// move up until you find a 0 ????????while (mat[row][col]) ????????????// if zero is not found in current column, ????????????// we are done ????????????if (--row < 0) ????????????????return count; ????????// add 0s present in current column to result ????????count += (row + 1); ????????// move right to next column ????????col++; ????} ????return count; } // Driver Program to test above functions int main() { ????int mat[N][N] = ????{ ????????{ 0, 0, 0, 0, 1 }, ????????{ 0, 0, 0, 1, 1 }, ????????{ 0, 1, 1, 1, 1 }, ????????{ 1, 1, 1, 1, 1 }, ????????{ 1, 1, 1, 1, 1 } ????}; ????cout << countZeroes(mat); ????return 0; } ``` ## Java ```java // Java program to count number of 0s in the given // row-wise and column-wise sorted binary matrix import java.io.*; class GFG? { ????public static int N = 5; ????// Function to count number of 0s in the given ????// row-wise and column-wise sorted binary matrix. ????static int countZeroes(int mat[][]) ????{ ????????// start from bottom-left corner of the matrix ????????int row = N - 1, col = 0; ????????// stores number of zeroes in the matrix ????????int count = 0; ????????while (col < N) ????????{ ????????????// move up until you find a 0 ????????????while (mat[row][col] > 0) ????????????????// if zero is not found in current column, ????????????????// we are done ????????????????if (--row < 0) ????????????????????return count; ????????????// add 0s present in current column to result ????????????count += (row + 1); ????????????// move right to next column ????????????col++; ????????} ????????return count; ????} ????// Driver program ????public static void main (String[] args)? ????{ ????????int mat[][] = { { 0, 0, 0, 0, 1 }, ????????????????????????{ 0, 0, 0, 1, 1 }, ????????????????????????{ 0, 1, 1, 1, 1 }, ????????????????????????{ 1, 1, 1, 1, 1 }, ????????????????????????{ 1, 1, 1, 1, 1 } }; ????????System.out.println(countZeroes(mat)); ????} } // This code is contributed by Pramod Kumar ``` ## Python ``` # Python program to count number? # of 0s in the given row-wise # and column-wise sorted? # binary matrix. # Function to count number? # of 0s in the given # row-wise and column-wise # sorted binary matrix. def countZeroes(mat): ????# start from bottom-left ????# corner of the matrix ????N = 5; ????row = N - 1; ????col = 0; ????# stores number of? ????# zeroes in the matrix ????count = 0; ????while (col < N): ????????# move up until ????????# you find a 0 ????????while (mat[row][col]): ????????????# if zero is not found? ????????????# in current column, we? ????????????# are done ????????????if (row < 0): ????????????????return count; ????????????row = row - 1; ????????# add 0s present in ????????# current column to result ????????count = count + (row + 1); ????????# move right to ????????# next column ????????col = col + 1; ????return count; # Driver Code mat = [[0, 0, 0, 0, 1], ???????[0, 0, 0, 1, 1], ???????[0, 1, 1, 1, 1], ???????[1, 1, 1, 1, 1], ???????[1, 1, 1, 1, 1]]; print( countZeroes(mat)); # This code is contributed # by chandan_jnu? ``` ## C# ```cs // C# program to count number of // 0s in the given row-wise and // column-wise sorted binary matrix using System; class GFG? { ????public static int N = 5; ????// Function to count number of? ????// 0s in the given row-wise and ????// column-wise sorted binary matrix. ????static int countZeroes(int [,] mat) ????{ ????????// start from bottom-left ????????// corner of the matrix ????????int row = N - 1, col = 0; ????????// stores number of zeroes? ????????// in the matrix ????????int count = 0; ????????while (col < N) ????????{ ????????????// move up until you find a 0 ????????????while (mat[row,col] > 0) ????????????????// if zero is not found in? ????????????????// current column, ????????????????// we are done ????????????????if (--row < 0) ????????????????????return count; ????????????// add 0s present in current? ????????????// column to result ????????????count += (row + 1); ????????????// move right to next column ????????????col++; ????????} ????????return count; ????} ????// Driver Code ????public static void Main ()? ????{ ????????int [,] mat = { { 0, 0, 0, 0, 1 }, ????????????????????????{ 0, 0, 0, 1, 1 }, ????????????????????????{ 0, 1, 1, 1, 1 }, ????????????????????????{ 1, 1, 1, 1, 1 }, ????????????????????????{ 1, 1, 1, 1, 1 } }; ????????Console.WriteLine(countZeroes(mat)); ????} } // This code is contributed by KRV. ``` ## PHP ```php <?php // PHP program to count number? // of 0s in the given row-wise // and column-wise sorted? // binary matrix. // Function to count number? // of 0s in the given // row-wise and column-wise // sorted binary matrix. function countZeroes($mat) { ????// start from bottom-left ????// corner of the matrix ????$N = 5; ????$row = $N - 1; ????$col = 0; ????// stores number of? ????// zeroes in the matrix ????$count = 0; ????while ($col < $N) ????{ ????????// move up until ????????// you find a 0 ????????while ($mat[$row][$col]) ????????????// if zero is not found? ????????????// in current column, we? ????????????// are done ????????????if (--$row < 0) ????????????????return $count; ????????// add 0s present in ????????// current column to result ????????$count += ($row + 1); ????????// move right to ????????// next column ????????$col++; ????} ????return $count; } // Driver Code $mat = array(array(0, 0, 0, 0, 1), ?????????????array(0, 0, 0, 1, 1), ?????????????array(0, 1, 1, 1, 1), ?????????????array(1, 1, 1, 1, 1), ?????????????array(1, 1, 1, 1, 1)); echo countZeroes($mat); // This code is contributed by Sam007 ?> ``` **輸出**： ``` 8 ``` **上述解決方案的時間復雜度**為 O（n ），因為解決方案遵循從矩陣的左下角到頂部或右側的單個路徑。 **程序使用的輔助空間**為`O(1)`。 如果您發現解決此問題的更多有趣方法，請與我們分享。