logo

TechCodeview

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.

  1. Diminua o índice da linha até encontrar 0. 
  2. 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.



mesas em látex

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.