ספירת אפסים בשורה חכמה ועמודה מטריצה ממוינת חכמה
בהינתן מטריצה בינארית N x n (אלמנטים במטריקס יכולים להיות 1 או 0) כאשר כל שורה ועמודה של המטריצה ממוינים במספר ספירת הסדר עולה של 0s שנמצאים בה.
דוגמאות:
קֶלֶט:
[0 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]
תְפוּקָה: 8
קֶלֶט:
[0 0]
[0 0]
תְפוּקָה: 4
קֶלֶט:
[1 1 1 1]
[1 1 1 1]
[1 1 1 1]
[1 1 1 1]
תְפוּקָה:
הרעיון פשוט מאוד. אנו מתחילים מהפינה השמאלית התחתונה של המטריצה וחוזרים על השלבים מתחת עד שנמצא את הקצה העליון או הימני של המטריצה.
- צמצום אינדקס השורה עד שנמצא 0.
- הוסף מספר 0 של 0s בעמודה הנוכחית, כלומר אינדקס השורה הנוכחי + 1 לתוצאה ועבר ימינה לעמודה הבאה (הגדל את אינדקס COL על ידי 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). מכיוון שלא נלקח מרחב נוסף.
