अवधारणा
0 और 1 के दिए गए सरणी के संबंध में, 1 के अधिकतम निरंतर अनुक्रम प्राप्त करने के लिए 0 की स्थिति को 1 से प्रतिस्थापित करने के लिए निर्धारित करें। इस मामले में, अपेक्षित समय जटिलता O(n) है और सहायक स्थान O(1) है।
इनपुट
arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1} आउटपुट
Index 10
सरणी अनुक्रमणिका को 0 से शुरू होने दें, 0 को 1 के साथ बदलें
अनुक्रमणिका 10 1s के सबसे लंबे निरंतर अनुक्रम का कारण बनती है।
इनपुट
arr[] = {1, 1, 1, 1, 1, 0} आउटपुट
Index 5
विधि
शून्य के दोनों ओर इकाईयों की संख्या का उपयोग करना −
अब, अवधारणा प्रत्येक शून्य के दोनों ओर लोगों की संख्या गिनने की है। यहां, आवश्यक सूचकांक को शून्य के सूचकांक के रूप में माना जाता है, जिसके चारों ओर अधिकतम संख्या होती है। इस उद्देश्य के संबंध में निम्नलिखित चर लागू किए गए हैं -
- leftCnt - इसका उपयोग वर्तमान तत्व के बाईं ओर की संख्या को शून्य पर विचार करने के लिए संग्रहीत करने के लिए किया जाता है।
- rightCnt - इसका उपयोग वर्तमान तत्व के दायीं ओर की संख्या को शून्य पर विचार करने के लिए संग्रहीत करने के लिए किया जाता है।
- maxIndex - इसे शून्य के सूचकांक के रूप में माना जाता है, जिसके चारों ओर अधिकतम संख्या होती है।
- lastInd - इसे देखे गए अंतिम शून्य तत्व का सूचकांक माना जाता है
- maxCnt - अगर इंडेक्स मैक्सइंड पर शून्य को एक से बदल दिया जाता है तो इसे लोगों की संख्या के रूप में माना जाता है।
अब प्रक्रिया विवरण नीचे दिया गया है -
-
जब तक कोई इनपुट ऐरे में मौजूद न हो तब तक राइटसेंट को बढ़ाना जारी रखें। मान लें कि अगला शून्य सूचकांक i पर मौजूद है।
-
सत्यापित करें कि यह शून्य तत्व पहला शून्य तत्व है या नहीं। अब इसे पहले शून्य तत्व के रूप में माना जाता है यदि lastInd में कोई मान्य अनुक्रमणिका मान नहीं है।
-
तो उस स्थिति में lastInd को अपडेट करना i के साथ किया जाता है। वर्तमान में rightCnt का मान इस शून्य के बाईं ओर के शून्यों की संख्या है।
-
इसके परिणामस्वरूप बाएँCnt, rightCnt के बराबर है और फिर फिर से rightCnt का मान निर्धारित करता है। यह देखा गया है कि यदि वर्तमान शून्य तत्व पहले शून्य नहीं है, तो सूचकांक lastInd पर मौजूद शून्य के आसपास की संख्या leftCnt + rightCnt द्वारा प्रदान की जाती है।
-
अब maxCnt मान लेफ्टCnt + rightCnt + 1 और maxIndex =lastInd को स्वीकार करेगा यदि यह मान वर्तमान में maxCnt द्वारा रखे गए मान से छोटा है।
-
वर्तमान में दायीं ओर इंडेक्स i पर बायीं ओर शून्य हो जाएगा और लास्टइंड i के बराबर होगा। अब फिर से rightCnt का मान निर्धारित करें, maxCnt वाले लोगों की संख्या की तुलना करें और उसके अनुसार maxCnt और maxIndex को अपडेट करें।
-
हमें इस प्रक्रिया को सरणी के प्रत्येक बाद के शून्य तत्व के लिए दोहराना होगा।
-
यह देखा गया है कि lastInd शून्य के सूचकांक को संग्रहीत करता है जिसके लिए वर्तमान बाएं और दाएं की गणना की जाती है।
-
अंत में, शून्य की आवश्यक अनुक्रमणिका को एक से बदलने के लिए maxIndex में संग्रहीत किया जाता है।
उदाहरण
// C++ program to find index of zero
// to be replaced by one to get longest
// continuous sequence of ones.
#include <bits/stdc++.h>
using namespace std;
// Used to returns index of 0 to be replaced
// with 1 to get longest continuous
// sequence of 1s. If there is no 0
// in array, then it returns -1.
int maxOnesIndex(bool arr1[], int n1){
int i = 0;
// Used to store count of ones on left
// side of current element zero
int leftCnt1 = 0;
// Used to store count of ones on right
// side of current element zero
int rightCnt1 = 0;
// Shows index of zero with maximum number
// of ones around it.
int maxIndex1 = -1;
// Shows index of last zero element seen
int lastInd1 = -1;
// Shows count of ones if zero at index
// maxInd1 is replaced by one.
int maxCnt1 = 0;
while (i < n1) {
// Used to keep incrementing count until
// current element is 1.
if (arr1[i]) {
rightCnt1++;
}
else {
// It has been observed that if current zero element
// is not first zero element,
// then count number of ones
// obtained by replacing zero at
// index lastInd. Update maxCnt
// and maxIndex if required.
if (lastInd1 != -1) {
if (rightCnt1 + leftCnt1 + 1 > maxCnt1) {
maxCnt1 = leftCnt1 + rightCnt1 + 1;
maxIndex1 = lastInd1;
}
}
lastInd1 = i;
leftCnt1 = rightCnt1;
rightCnt1 = 0;
}
i++;
}
// Determine number of ones in continuous
// sequence when last zero element is
// replaced by one.
if (lastInd1 != -1) {
if (leftCnt1 + rightCnt1 + 1 > maxCnt1) {
maxCnt1 = leftCnt1 + rightCnt1 + 1;
maxIndex1 = lastInd1;
}
}
return maxIndex1;
}
// Driver function
int main(){
bool arr1[] = { 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1 };
// bool arr1[] = {1, 1, 1, 1, 1, 0};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
cout << "Index of 0 to be replaced is "
<< maxOnesIndex(arr1, n1);
return 0;
} आउटपुट
Index of 0 to be replaced is 10