logo

TechCodeview

Räkna nollor i radmässigt och kolumnmässigt sorterade matris

Med tanke på en n x n binär matris (element i matris kan vara antingen 1 eller 0) där varje rad och kolumn i matrisen sorteras i stigande orderantal Antal 0s närvarande i den.

Exempel:  



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]
Produktion: 8

Input:
[0 0]
[0 0]
Produktion: 4

Input:
[1 1 1 1]
[1 1 1 1]
[1 1 1 1]
[1 1 1 1]
Produktion:

Idén är väldigt enkel. Vi börjar från det nedre vänstra hörnet av matrisen och upprepar stegen tills vi hittar den övre eller högra kanten på matrisen.

  1. MECREMENT ROW INDEX tills vi hittar en 0. 
  2. Lägg till antal 0s i den aktuella kolumnen, dvs aktuell radindex + 1 till resultatet och flytta till nästa kolumn (inkrement Col Index med 1).

Ovanstående logik fungerar eftersom matrisen är radmässigt och kolumnmässigt sorterat. Logiken fungerar också för alla matriser som innehåller icke-negativa heltal.



Nedan är implementeringen av ovanstående idé:

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));

Produktion 
8

Tidskomplexitet Av ovanstående lösning är O (n) eftersom lösningen följer en enda väg från nedre vänster hörn till toppen eller höger kant på matrisen. 
Hjälputrymme som används av programmet är O (1). Eftersom inget extra utrymme har tagits.