Satır bazında ve sütun bazında sıralanmış matriste sıfırları sayın
Bir n x n ikili matris verildiğinde (matristeki öğeler 1 veya 0 olabilir), burada matrisin her satırı ve sütunu, içinde mevcut olan 0'ların artan sırasına göre sıralanır.
Örnekler:
Giriş:
[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]
Çıkış: 8
Giriş:
[0 0]
[0 0]
Çıkış: 4
Giriş:
[1 1 1 1]
[1 1 1 1]
[1 1 1 1]
[1 1 1 1]
Çıkış:
Fikir çok basit. Matrisin sol alt köşesinden başlıyoruz ve matrisin üst veya sağ kenarını bulana kadar aşağıdaki adımları tekrarlıyoruz.
- 0 bulana kadar satır indeksini azaltın.
- Sonuca geçerli sütundaki 0 sayısını, yani geçerli satır dizini + 1'i ekleyin ve sağa doğru sonraki sütuna geçin (Sütun dizini 1 artırın).
Matris satır ve sütun bazında sıralandığından yukarıdaki mantık işe yarayacaktır. Mantık aynı zamanda negatif olmayan tamsayılar içeren herhangi bir matris için de çalışacaktır.
Aşağıda yukarıdaki fikrin uygulanması yer almaktadır:
C++ #include #include using namespace std ; // Function to count number of 0s in the given // row-wise and column-wise sorted binary matrix. int countZeroes ( const vector < vector < int >>& mat ) { int n = mat . size (); // start from the bottom-left corner int row = n - 1 col = 0 ; int count = 0 ; while ( col < n ) { // move up until you find a 0 while ( row >= 0 && mat [ row ][ col ]) { row -- ; } // add the number of 0s in the current // column to the result count += ( row + 1 ); // move to the next column col ++ ; } return count ; } int main () { vector < vector < 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 } }; cout < < countZeroes ( mat ); return 0 ; }
C // C program to count number of 0s in the given // row-wise and column-wise sorted binary matrix. #include // 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 } }; printf ( '%d' countZeroes ( mat )); return 0 ; }
Java import java.util.Arrays ; public class GfG { // Function to count number of 0s in the given // row-wise and column-wise sorted binary matrix. public static int countZeroes ( int [][] mat ) { int n = mat . length ; // start from the bottom-left corner int row = n - 1 col = 0 ; int count = 0 ; while ( col < n ) { // move up until you find a 0 while ( row >= 0 && mat [ row ][ col ] == 1 ) { row -- ; } // add the number of 0s in the current // column to the result count += ( row + 1 ); // move to the next column col ++ ; } return count ; } 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 )); } }
Python # Function to count number of 0s in the given # row-wise and column-wise sorted binary matrix. def count_zeroes ( mat ): n = len ( mat ) # start from the bottom-left corner row = n - 1 col = 0 count = 0 while col < n : # move up until you find a 0 while row >= 0 and mat [ row ][ col ]: row -= 1 # add the number of 0s in the current # column to the result count += ( row + 1 ) # move to the next column col += 1 return count if __name__ == '__main__' : 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 ( count_zeroes ( mat ))
C# // Function to count number of 0s in the given // row-wise and column-wise sorted binary matrix. using System ; using System.Collections.Generic ; class Program { static int CountZeroes ( int [] mat ) { int n = mat . GetLength ( 0 ); // start from the bottom-left corner int row = n - 1 col = 0 ; int count = 0 ; while ( col < n ) { // move up until you find a 0 while ( row >= 0 && mat [ row col ] == 1 ) { row -- ; } // add the number of 0s in the current // column to the result count += ( row + 1 ); // move to the next column col ++ ; } return count ; } 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 )); } }
JavaScript // Function to count number of 0s in the given // row-wise and column-wise sorted binary matrix. function countZeroes ( mat ) { const n = mat . length ; // start from the bottom-left corner let row = n - 1 col = 0 ; let count = 0 ; while ( col < n ) { // move up until you find a 0 while ( row >= 0 && mat [ row ][ col ]) { row -- ; } // add the number of 0s in the current // column to the result count += ( row + 1 ); // move to the next column col ++ ; } return count ; } const 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 . log ( countZeroes ( mat ));
Çıkış
8
Zaman karmaşıklığı Yukarıdaki çözüm O(n)'dir çünkü çözüm, matrisin sol alt köşesinden üst veya sağ kenarına kadar tek yol takip eder.
Yardımcı alan programın kullandığı O(1)'dir. fazladan yer alınmadığından.
