समस्या विवरण
इस समस्या में, हमें एक बाइनरी मैट्रिक्स दिया गया है जहां प्रत्येक पंक्ति के तत्व क्रमबद्ध हैं। हमारा कार्य अधिकतम 1 वाली पंक्ति खोजना है।
उदाहरण
इनपुट
mat[][] = {{0, 1, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 1},
{0, 0, 1, 1}}
आउटपुट
1
व्याख्या
मैट्रिक्स की प्रत्येक पंक्ति में 1 की गिनती: पंक्ति 0: 3 पंक्ति 1: 4 पंक्ति 2: 1 पंक्ति 3: 2
हल का दृष्टिकोण
समस्या का एक सरल समाधान पहली 1 के सबसे छोटे इंडेक्स वाली पंक्ति खोजना है।
एक दृष्टिकोण पंक्ति-वार पार करके पहली 1 का इंडेक्स खोजना है जो पंक्ति में अधिकतम 1 की गिनती लौटाएगा। और फिर हम अधिकतम 1 वाली पंक्ति वापस करेंगे।
एक अन्य दृष्टिकोण बाइनरी खोज का उपयोग करके प्रत्येक पंक्ति में पहली 1 की घटना खोजना है। फिर हम अधिकतम 1 वाले मान को वापस करेंगे।
C++ कार्यान्वयन (बाइनरी खोज)
#include <iostream>
using namespace std;
#define R 4
#define C 4
int findFirst1BinSearch(bool arr[], int low, int high) {
if (high >= low) {
int mid = low + (high - low) / 2;
if ((mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
return mid;
else if (arr[mid] == 0)
return findFirst1BinSearch(arr, (mid + 1), high);
else
return findFirst1BinSearch(arr, low, (mid - 1));
}
return -1;
}
int findMaxOneRow(bool mat[R][C]) {
int max1RowIndex = 0, maxCount = -1;
for (int i = 0; i < R; i++) {
int first1Index = findFirst1BinSearch(mat[i], 0, C-1);
if (first1Index != -1 && C - first1Index > maxCount) {
maxCount = C - first1Index;
max1RowIndex = i;
}
}
return max1RowIndex;
}
int main() {
bool mat[R][C] = {{0, 1, 1, 1},
{1, 1, 1, 1},
{0, 0, 1, 1},
{0, 0, 0, 1}};
cout << "मैट्रिक्स में अधिकतम 1 वाली पंक्ति है " << findMaxOneRow(mat);
return 0;
}
आउटपुट
मैट्रिक्स में अधिकतम 1 वाली पंक्ति है 1
जटिलता विश्लेषण
- समय जटिलता: O(R log C) - R पंक्तियों के लिए बाइनरी खोज
- स्पेस जटिलता: O(log C) - पुनरावर्ती स्टैक के कारण
अनुकूलन नोट
इसे O(R + C) में एक पॉइंटर का उपयोग करके हल किया जा सकता है जो शीर्ष-दाएं कोने से शुरू होता है और बाएं/नीचे जाता है, लेकिन बाइनरी खोज दृष्टिकोण समझने में आसान है और सामान्य सीमाओं के लिए पर्याप्त तेज़ है।
