Conte zeros em uma matriz classificada por linha e por coluna
Dada uma matriz binária n x n (os elementos da matriz podem ser 1 ou 0), onde cada linha e coluna da matriz é classificada em ordem crescente, contando o número de 0s presentes nela.
Exemplos:
Entrada:
[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]
Saída: 8
Entrada:
[0 0]
[0 0]
Saída: 4
Entrada:
[1 1 1 1]
[1 1 1 1]
[1 1 1 1]
[1 1 1 1]
Saída:
A ideia é muito simples. Começamos no canto inferior esquerdo da matriz e repetimos as etapas abaixo até encontrar a borda superior ou direita da matriz.
- Diminua o índice da linha até encontrar 0.
- Adicione o número de 0s na coluna atual, ou seja, o índice da linha atual + 1 ao resultado e vá para a direita para a próxima coluna (incremente o índice da coluna em 1).
A lógica acima funcionará, pois a matriz é classificada por linha e por coluna. A lógica também funcionará para qualquer matriz contendo números inteiros não negativos.
Abaixo está a implementação da ideia acima:
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 ));
Saída
8
Complexidade de tempo da solução acima é O(n), uma vez que a solução segue um caminho único do canto inferior esquerdo até a borda superior ou direita da matriz.
Espaço auxiliar usado pelo programa é O(1). já que nenhum espaço extra foi ocupado.
