在按行和按列排序的矩阵中计算零-yiteyi-C++库

给定一个nxn二进制矩阵（矩阵中的元素可以是1或0），其中矩阵的每一行和每一列按升序排序，计算其中存在的0的数量。预期时间复杂度为O（N）。 例如：

null

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: 8Input: [0, 0][0, 0]Output: 4Input: [1, 1, 1, 1][1, 1, 1, 1][1, 1, 1, 1][1, 1, 1, 1]Output: 0

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

这个想法很简单。我们从矩阵的左下角开始，重复以下步骤，直到找到矩阵的上边缘或右边缘。 1.递减行索引，直到找到0。 2.将当前列中的0数（即当前行索引+1）添加到结果中，并向右移动到下一列（将列索引增加1）。上述逻辑将起作用，因为矩阵是按行和按列排序的。该逻辑也适用于任何包含非负整数的矩阵。以下是上述理念的实施：

C++

                         // 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 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#

                         // 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 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                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to count number of 0s in the given                       
                         // row-wise and column-wise sorted binary matrix                       
           
                                                 let N = 5;                       
                                   
                                                 // 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                       
                                                 let row = N - 1, col = 0;                       
                                   
                                                 // stores number of zeroes in the matrix                       
                                                 let 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                       
           
                                                 let 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 ]];                       
                                                 document.write(countZeroes(mat));                       
           
                         </script>                       

输出：

时间复杂性 因为解遵循从矩阵左下角到上边缘或右边缘的单一路径，所以上述解的形式为O（n）。 辅助空间 程序使用的是O（1）。如果你能找到更有趣的方法来解决这个问题，请与我们分享。本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章