सन्निहित ऐरे


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना MakeMyTrip मॉर्गन स्टेनली Paytm
hashing फिसलने वाली खिडकी

दिया गया सरणी जिसमें नंबर 0 और 1 का समावेश है। हमें सबसे लंबी सन्निहित उप-सरणी की लंबाई को ढूंढना है जिसमें ओ का और 1 का समान है।

उदाहरण

निवेश

गिरफ्तार = [0,1,0,1,0,0,1]

उत्पादन

6

व्याख्या

सबसे लंबा सन्निहित उप-सरणी लाल रंग में चिह्नित है [0,1,0,1,0,0,1] और इसकी लंबाई 6 है।

कलन विधि

  1. अधिकतम 0 का मान सेट करें।
  2. दो लूप का उपयोग करें, पहले लूप सेट में zer_count to 0, one_count to 0।
  3. यदि का मान एक विशेष सूचकांक में सरणी 0 पाया जाता है फिर 1 से शून्य_काउंट बढ़ाएं।
  4. अपडेट अपडेट करें और one_count को 1 से बढ़ाएं।
  5. प्रत्येक पुनरावृत्ति जाँच में, यदि शून्य_काउंट one_count के बराबर है, यदि बराबर है, तो पता करें कि बीच में कोई बड़ा नहीं है (अधिकतमलेन और j-i + 1)
  6. अधिकतम लौटें

व्याख्या

हमारा मुख्य विचार सबसे लंबे समय तक सन्निहित सब्रे की लंबाई खोजना है जिसमें शून्य और केवल एक है, इसलिए हमारा मुख्य ध्यान उस लंबाई को खोजना है।

इसलिए, हम लूप के लिए नेस्टेड का उपयोग करने जा रहे हैं। बाहरी लूप में, हम शून्य_काउंट और one_count के मान को 0 में आरंभीकृत करते हैं, क्योंकि प्रत्येक पुनरावृत्ति के बाद जब यह आंतरिक लूप से बाहर आता है, तो हमें फिर से यह देखने के लिए शून्य_count और one_count के नए मूल्यों की आवश्यकता होती है। हम लूप पर पुनरावृति करने जा रहे हैं जब तक कि सरणी की लंबाई नहीं हो जाती।

अब यह सरणी के प्रत्येक एकल मान की जाँच करने जा रहा है, यदि गिरफ्तारी [सूचकांक] का मान ० या १ है, यदि इसका मान ० के बराबर है तो अद्यतन करें और शून्य_ मान को १ से बढ़ाएँ या यदि गिरफ्तारी का मूल्य [सूचकांक] पाया जाता है कि यह 0 है, फिर यह अपडेट होता है और 1 से one_count का मान बढ़ाता है।

अब, अगला यदि ब्लॉक की जाँच करने जा रहा है यदि शून्य_काउंट one_count के बराबर है, यदि बराबर है, तो अधिकतम संख्या और j-i + 1 के बीच की बड़ी संख्या ज्ञात करें और बड़ी संख्या को maxlen में संग्रहीत करता है।

उदाहरण

मान लिया गया सरणी: गिरफ्तारी [] = {1,0,0,1,0,1,0}

zero_count = 0, one_count = 0, maxlen = 0

i = 0 पर, => j = i

ज = ६

गिरफ्तार होने पर [j] 0 के बराबर नहीं, तो one_count ++, का अर्थ one_count = 1 है

ज = ६

गिरफ्तार होने पर [जे] 0 के बराबर, फिर शून्य_काउंट ++, मतलब शून्य_कोाउंट = 1

इस स्थान पर यदि ब्लॉक निष्पादित किया जाता है, तो यह अधिकतम, और j-i + 1 के बीच बड़ा नहीं देता है और अधिकतम 2 में देता है

ज = ६

गिरफ्तार होने पर [जे] 0 के बराबर, फिर शून्य_काउंट ++, मतलब शून्य_कोाउंट = 2

ज = ६

गिरफ्तार होने पर [j] 0 के बराबर नहीं, तो one_count ++, का अर्थ one_count = 2 है

इस स्थान पर अगर ब्लॉक निष्पादित किया जाता है, तो यह अधिकतम, और j-i + 1 के बीच बड़ा नहीं देता है और अधिकतम 4 में रिटर्न करता है।

ज = ६

गिरफ्तार होने पर [जे] 0 के बराबर, फिर शून्य_काउंट ++, मतलब शून्य_कोाउंट = 3

ज = ६

गिरफ्तार होने पर [j] 0 के बराबर नहीं, तो one_count ++, का अर्थ one_count = 3 है

इस स्थान पर अगर ब्लॉक निष्पादित किया जाता है, तो यह अधिकतम, और j-i + 1 के बीच बड़ा नहीं देता है और अधिकतम 6 में रिटर्न करता है।

ज = ६

गिरफ्तार होने पर [जे] 0 के बराबर, फिर शून्य_काउंट ++, मतलब शून्य_कोाउंट = 4

और यह लूप को पुनरावृत्त करता रहता है जब तक कि सभी स्थितियां विफल नहीं होंगी।

और 6 के रूप में अधिकतम रिटर्न।

कार्यान्वयन

Contiguous Array के लिए C ++ प्रोग्राम

#include <iostream>
using namespace std;
int contiguous_Array(int arr[], int n)
{
    int i,j,maxlen=0;
    for( i = 0 ; i < n ; i++)
    {
        int zero_count=0,one_count=0;
        for(j = i ; j < n ; j++)
        {
            if( arr[j] == 0 )
            {
                zero_count++;
            }
            else
            {
                one_count++;
            }
            if(zero_count==one_count)
            {
                maxlen=std::max(maxlen,j-i+1);
            }
        }
    }
    return maxlen;
}
int main()
{
    int arr[]= {1,0,0,1,0,1,0};
    int n=sizeof(arr)/sizeof(arr[0]);
    cout <<contiguous_Array(arr,n)<< endl;
    return 0;
}
6

कंट्रेग्युअस ऐरे के लिए जावा प्रोग्राम

public class Contiguous_Array {

  public static int solution(int[] arr) {

    int maxlen = 0;

    for (int i = 0; i<arr.length; i++) {

      int zero_count = 0, one_count = 0;

      for (int j = i; j<arr.length; j++) {

        if (arr[j] == 0) {
          zero_count++;
        } else {
          one_count++;
        }
        if (zero_count == one_count) {

          maxlen = Math.max(maxlen, j - i + 1);

        }
      }
    }
    return maxlen;
  }
  public static void main(String args[]) {

    int[] arr = new int[] {
      0, 1, 0, 1, 0, 0, 1
    };

    System.out.println(solution(arr));

  }
}
6

जटिल सरणी के लिए जटिलता विश्लेषण

समय जटिलता

ओ (एन * एन) जहां N दिए गए सरणी का आकार है।

अंतरिक्ष जटिलता

ओ (1) क्योंकि हम यहाँ किसी अतिरिक्त स्थान का उपयोग नहीं करते हैं।

संदर्भ