अवधारणा
0s और 1s की दी गई सरणी के संबंध में, 0 की स्थिति निर्धारित करें जिसे 1 से बदलकर 1s का अधिकतम सतत अनुक्रम प्राप्त किया जा सके। इस मामले में, अपेक्षित समय जटिलता 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
विधि
शून्य के दोनों किनारों पर 1s की गिनती का उपयोग करके −
अब, अवधारणा प्रत्येक शून्य के दोनों किनारों पर 1s की संख्या गिनना है। यहां, आवश्यक इंडेक्स को उस शून्य के इंडेक्स के रूप में माना जाता है जिसके चारों ओर अधिकतम संख्या में 1s हैं। निम्नलिखित चर इस उद्देश्य के लिए लागू किए जाते हैं −
- leftCnt − वर्तमान विचाराधीन शून्य तत्व के बाईं ओर 1s की गिनती संग्रहीत करने के लिए उपयोग किया जाता है।
- rightCnt − वर्तमान विचाराधीन शून्य तत्व के दाईं ओर 1s की गिनती संग्रहीत करने के लिए उपयोग किया जाता है।
- maxIndex − इसे उसके चारों ओर अधिकतम संख्या में 1s वाले शून्य के इंडेक्स के रूप में माना जाता है।
- lastInd − देखे गए अंतिम शून्य तत्व के इंडेक्स के रूप में माना जाता है
- maxCnt − इसे 1s की गिनती के रूप में माना जाता है यदि इंडेक्स maxInd पर शून्य को एक से बदल दिया जाता है।
अब प्रक्रिया विवरण नीचे दिए गए हैं −
rightCnt को तब तक बढ़ाते रहें जब तक इनपुट सरणी में 1 मौजूद है। मान लें अगला शून्य इंडेक्स i पर मौजूद है।
सत्यापित करें कि यह शून्य तत्व पहला शून्य तत्व है या नहीं। अब इसे पहला शून्य तत्व माना जाता है यदि lastInd कोई वैध इंडेक्स मान नहीं रखता है।
तो उस स्थिति में lastInd को i से अपडेट किया जाता है। वर्तमान में rightCnt का मान इस शून्य के बाईं ओर शून्य की संख्या है।
इसके परिणामस्वरूप leftCnt, rightCnt के बराबर है और फिर फिर से rightCnt का मान निर्धारित करें। यह देखा गया है कि यदि वर्तमान शून्य तत्व पहला शून्य नहीं है, तो इंडेक्स lastInd पर मौजूद शून्य के चारों ओर 1s की संख्या leftCnt + rightCnt द्वारा दी जाती है।
अब maxCnt, leftCnt + rightCnt + 1 का मान स्वीकार करेगा और maxIndex = lastInd यदि यह मान वर्तमान में maxCnt द्वारा रखे गए मान से छोटा है।
- <प>वर्तमान में rightCnt, इंडेक्स i पर शून्य के लिए leftCnt बन जाएगा और lastInd, i के बराबर होगा। अब फिर से rightCnt का मान निर्धारित करें, 1s की संख्या की तुलना maxCnt से करें और तदनुसार maxCnt और maxIndex को अपडेट करें।
- <प>इस प्रक्रिया को सरणी के प्रत्येक बाद के शून्य तत्व के लिए दोहराएं। <ली><प>यह देखा गया है कि lastInd उस शून्य का इंडेक्स संग्रहीत करता है जिसके लिए वर्तमान leftCnt और rightCnt की गणना की जाती है।<ली><प>अंत में, 1 से बदले जाने वाले शून्य का आवश्यक इंडेक्स 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; // 0 के इंडेक्स को लौटाता है जिसे // 1 से बदलकर 1s का सबसे लंबा // सतत अनुक्रम प्राप्त किया जा सके। यदि सरणी में कोई 0 नहीं है, तो यह -1 लौटाता है। int maxOnesIndex(bool arr1[], int n1){ int i = 0; // वर्तमान तत्व शून्य के बाईं ओर 1s की गिनती संग्रहीत करने के लिए उपयोग किया जाता है int leftCnt1 = 0; // वर्तमान तत्व शून्य के दाईं ओर 1s की गिनती संग्रहीत करने के लिए उपयोग किया जाता है int rightCnt1 = 0; // उसके चारों ओर अधिकतम संख्या में 1s वाले शून्य का इंडेक्स दिखाता है। int maxIndex1 = -1; // देखे गए अंतिम शून्य तत्व का इंडेक्स दिखाता है int lastInd1 = -1; // यदि इंडेक्स maxInd1 पर शून्य को एक से बदल दिया जाता है तो 1s की गिनती दिखाता है। int maxCnt1 = 0; while (i < n1) { // वर्तमान तत्व 1 होने तक गिनती बढ़ाते रहने के लिए उपयोग किया जाता है। if (arr1[i]) { rightCnt1++; } else { // यह देखा गया है कि यदि वर्तमान शून्य तत्व // पहला शून्य तत्व नहीं है, // तो इंडेक्स पर शून्य को बदलकर प्राप्त 1s की संख्या गिनें // lastInd। आवश्यकतानुसार maxCnt // और maxIndex को अपडेट करें। if (lastInd1 != -1) { if (rightCnt1 + leftCnt1 + 1 > maxCnt1) { maxCnt1 = leftCnt1 + rightCnt1 + 1; maxIndex1 = lastInd1; } } lastInd1 = i; leftCnt1 = rightCnt1; rightCnt1 = 0; } i++; } // जब अंतिम शून्य तत्व को एक से बदला जाता है तो // सतत अनुक्रम में 1s की संख्या निर्धारित करें। if (lastInd1 != -1) { if (leftCnt1 + rightCnt1 + 1 > maxCnt1) { maxCnt1 = leftCnt1 + rightCnt1 + 1; maxIndex1 = lastInd1; } } return maxIndex1; } // ड्राइवर फ़ंक्शन 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
