logo

TechCodeview

Gróf nullák sorba sorban és oszlop bölcs és bölcs mátrix

Adva egy n x n bináris mátrixot (a mátrix elemei lehetnek 1 vagy 0 lehetnek), ahol a mátrix minden sorát és oszlopát növekvő sorrendben sorolják be a benne lévő 0 -os szám.

Példák:  



Bemenet:
[0 0 0 0 1]
[0 0 0 1 1 1]
[0 1 1 1 1]
[1 1 1 1 1]
[1 1 1 1 1]
Kimenet: 8

Bemenet:
[0 0]
[0 0]
Kimenet: 4

Bemenet:
[1 1 1 1]
[1 1 1 1]
[1 1 1 1]
[1 1 1 1]
Kimenet:

Az ötlet nagyon egyszerű. A mátrix bal alsó sarkától kezdjük, és megismételjük a lépések alatt, amíg meg nem találjuk a mátrix felső vagy jobb szélét.

  1. Csökkentse a sorindexet, amíg nem találunk 0 -t. 
  2. Adja hozzá a 0 -os számot az aktuális oszlopba, azaz az aktuális sorindex + 1 -et az eredményhez, és mozgassa jobbra a következő oszlopba (a tőkés -index 1 -vel).

A fenti logika működni fog, mivel a mátrix sorban és oszlop szerint rendezve van. A logika bármilyen mátrixon is működni fog, amely nem negatív egész számokat tartalmaz.



Az alábbiakban bemutatjuk a fenti ötlet megvalósítását:

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

Kibocsátás 
8

Idő bonyolultság A fenti oldat o (n), mivel az oldat az egyetlen útvonalat követi a bal alsó sarok sarkától a mátrix felső vagy jobb széléig. 
Segédterület A program által használt o (1). Mivel nem került extra hely.