행 방향 및 열 방향으로 정렬된 행렬에서 0 계산
n x n 이진 행렬(행렬의 요소는 1 또는 0일 수 있음)이 주어지면 행렬의 각 행과 열은 그 안에 존재하는 0의 수를 카운트하여 오름차순으로 정렬됩니다.
예:
입력:
[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]
산출: 8
입력:
[0 0]
[0 0]
산출: 4
입력:
[1 1 1 1]
[1 1 1 1]
[1 1 1 1]
[1 1 1 1]
산출:
아이디어는 매우 간단합니다. 행렬의 왼쪽 아래 모서리부터 시작하여 행렬의 위쪽 또는 오른쪽 가장자리를 찾을 때까지 아래 단계를 반복합니다.
- 0을 찾을 때까지 행 인덱스를 감소시킵니다.
- 현재 열에 0의 수를 추가합니다. 즉, 현재 행 인덱스 + 1을 결과에 추가하고 다음 열로 오른쪽으로 이동합니다(열 인덱스를 1씩 증가).
위의 논리는 행렬이 행 방향 및 열 방향으로 정렬되므로 작동합니다. 이 논리는 음수가 아닌 정수를 포함하는 모든 행렬에서도 작동합니다.
다음은 위의 아이디어를 구현한 것입니다.
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 ));
산출
8
시간 복잡도 위 솔루션은 솔루션이 왼쪽 하단 모서리에서 행렬의 상단 또는 오른쪽 가장자리까지 단일 경로를 따르기 때문에 O(n)입니다.
보조 공간 프로그램에서 사용되는 것은 O(1)입니다. 추가 공간을 차지하지 않았기 때문입니다.
