इस समस्या में, हमें एक बाइनरी मैट्रिक्स दिया गया है जिसमें प्रत्येक पंक्ति सॉर्टेड है। हमारा कार्य बाइनरी मैट्रिक्स की उस पंक्ति की संख्या खोजना है जिसमें अधिकतम संख्या में 1s हों।
आइए एक उदाहरण से इस समस्या को समझते हैं,
इनपुट
binMat[][] = { 1, 1, 1, 1 0, 0, 0, 0 0, 0, 0, 1 0, 0, 1, 1 }आउटपुट
1
समाधान दृष्टिकोण
इस समस्या का एक सरल समाधान प्रत्येक पंक्ति में कुल 1s की गिनती करना है। और फिर अधिकतम 1 काउंट वाली पंक्ति संख्या वापस करना है।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
उदाहरण
#include <iostream> using namespace std; #define R 4 #define C 4 int findMax1Row(bool mat[R][C]) { int max1Row = 0, max1Count = -1; int i, index; for (i = 0; i < R; i++) { int oneCount = 0; for(int j = 0; j < C; j++){ if(mat[i][j]) oneCount++; } if(oneCount > max1Count){ max1Count = oneCount; max1Row = i; } } return (max1Row + 1); } int main() { bool mat[R][C] = { {0, 1, 1, 1}, {0, 0, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0} }; cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat); return 0; }आउटपुट
The number of row with maximum number of 1's is 1 एक बेहतर समाधान प्रत्येक पंक्ति पर बाइनरी सर्च का उपयोग करके पंक्ति में 1 की पहली घटना को ढूंढना हो सकता है। पंक्ति में 1s की संख्या पंक्ति आकार - पहली 1 के इंडेक्स का उपयोग करके पाई जा सकती है। इसका उपयोग करके, हम प्रत्येक पंक्ति में 1s की संख्या ढूंढ सकते हैं और फिर अधिकतम 1s वाली पंक्ति वापस कर सकते हैं।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
उदाहरण
#include <iostream> using namespace std; #define R 4 #define C 4 int binarySearch1Row(bool arr[], int start, int end) { if(end >= start) { int mid = start + (end - start)/2; if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1) return mid; else if (arr[mid] == 0) return binarySearch1Row(arr, (mid + 1), end); else return binarySearch1Row(arr, start, (mid -1)); } return -1; } int findMax1Row(bool mat[R][C]) { int max1Row = 0, max1Count = -1; int i, index; for (i = 0; i < R; i++) { index = binarySearch1Row(mat[i], 0, C-1); if (index != -1 && ( C-index) > max1Count) { max1Count = C - index; max1Row = i; } } return (max1Row + 1); } int main() { bool mat[R][C] = { {0, 1, 1, 1}, {0, 0, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0} }; cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat); return 0; }आउटपुट
The number of row with maximum number of 1's is 1
उपरोक्त दृष्टिकोण में एक अनुकूलन जोड़ा जा सकता है यह जांचना कि क्या वर्तमान पंक्ति में पिछली पंक्ति से अधिक 1s हैं, पहली 1 के इंडेक्स का उपयोग करके। यदि इसमें अधिक 1s हैं तो बाइनरी सर्च करें लेकिन 0 से पिछली पंक्ति में पहली 1 के इंडेक्स तक।
यह वर्तमान से कम 1s वाली पंक्ति में 1s की संख्या की गणना के ओवरहेड को बचाएगा।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
उदाहरण
#include <iostream> using namespace std; #define R 4 #define C 4 int binarySearch1Row(bool arr[], int start, int end) { if(end >= start) { int mid = start + (end - start)/2; if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1) return mid; else if (arr[mid] == 0) return binarySearch1Row(arr, (mid + 1), end); else return binarySearch1Row(arr, start, (mid -1)); } return -1; } int findMax1Row(bool mat[R][C]) { int i, index; int max1Row = 0; int max1Count = binarySearch1Row(mat[0], 0, C - 1); for (i = 1; i < R; i++){ if (max1Count != -1 && mat[i][C - max1Count - 1] == 1) { index = binarySearch1Row (mat[i], 0, C - max1Count); if (index != -1 && C - index > max1Count) { max1Count = C - index; max1Row = i; } } else max1Count = binarySearch1Row(mat[i], 0, C - 1); } return (max1Row + 1); } int main() { bool mat[R][C] = { {0, 1, 1, 1}, {0, 0, 0, 1}, {0, 0, 1, 1}, {0, 0, 0, 0} }; cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat); return 0; }आउटपुट
The number of row with maximum number of 1's is 1
