عد الأصفار في مصفوفة مرتبة حسب الصف والعمود
بالنظر إلى مصفوفة ثنائية n x n (يمكن أن تكون العناصر الموجودة في المصفوفة إما 1 أو 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.
- أضف عددًا من الأصفار في العمود الحالي، أي فهرس الصف الحالي + 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). لأنه لم يتم أخذ مساحة إضافية.
