मिल्दो एरे


कठिनाई तह मध्यम
बारम्बार सोधिन्छ अमेजन MakeMyTrip मोर्गन स्टेनले पेटम
ह्याशिंग स्लाइडि Wind विन्डो

दिइएको array नम्बर ० र १ को मात्र समावेश गर्दछ। हामीले सबैभन्दा लामो मिल्दो उप-एर्रे को लम्बाई पत्ता लगाउनु पर्छ जसमा ओ र १ बराबर हुन्छ।

उदाहरणका

आगत

arr = [,,२,0,1,0,1,0,0,1,१,२,०,XNUMX,१०,२,XNUMX,०,XNUMX,०,XNUMX,०]

उत्पादन

6

स्पष्टीकरण

सबै भन्दा लामो मिल्दो उप-एर्रे रातो [०,1,0,1,0,0,1] र यसको लम्बाई is हो।

अल्गोरिदम

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

स्पष्टीकरण

हाम्रो मुख्य विचार भनेको सब भन्दा लामो मिल्दो सुभर्रेको लम्बाइ पत्ता लगाउनु हो जुन शून्यको हो र एउटा मात्र हो, त्यसैले हाम्रो मुख्य फोकस भनेको त्यो लम्बाई पत्ता लगाउनु हो।

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

अब यसले एर्रेको प्रत्येक मानलाई जाँच्न गइरहेको छ, यदि एरर [अनुक्रमणिका] को मान ० वा १ छ यदि यसको मान ० बराबर छ भने अपडेट र शून्य_कउन्टको मान १ बढाउँदै बढाए वा एर [अनुक्रमणिका] को मान १ भएको पाउँदछ, त्यसपछि यो अद्यावधिक हुन्छ र वन_कउन्टको मान १ बढाउँदछ।

अब, यदि अर्को ब्लक जाँच्न जाँदै छ कि शून्य_काउन्ट एक_कउन्टमा बराबर छ, यदि बराबर छ भने, त्यसपछि म्याक्सलेन र j-i + १ बिचको ठूलो संख्या फेला पार्नुहोस् र म्याक्सलेनमा ठूलो नम्बर भण्डार गर्दछ।

उदाहरणका

मानौं एर्रे दिइएको छ: एर [] = {१,०,०,१,०,१,०}

शून्य_गणना = ०, one_count = ०, अधिकतम = ०

i = 0, => j = i मा

j = ०

एर [j] ० सँग बराबर छैन, त्यसपछि one_count ++, मतलब one_count = १ हो

j = ०

एर [j] ० लाई बराबर, त्यसपछि शुन्य_क +्ग ++, को मतलब शून्य_गणना = १

यस ठाउँमा अर्को ब्लक कार्यान्वयन भएमा, यसले म्याग्लेन र j-i + १ बिच ठूला नम्बर दिन्छ र म्याक्सलेनमा २ फिर्ता दिन्छ।

j = ०

एर [j] ० लाई बराबर, त्यसपछि शुन्य_क +्ग ++, को मतलब शून्य_गणना = १

j = ०

एरमा [j] ० बराबर छैन, त्यसपछि one_count ++, मतलब one_count = २

यस ठाउँमा अर्को ब्लक कार्यान्वयन भएमा, यसले म्याग्लेन र j-i + १ बिच ठूलो नो दिन्छ र max लाई म्याग्लेनमा फर्काउँछ।

j = ०

एर [j] ० लाई बराबर, त्यसपछि शुन्य_क +्ग ++, को मतलब शून्य_गणना = १

j = ०

एरमा [j] ० बराबर छैन, त्यसपछि one_count ++, मतलब one_count = २

यस ठाउँमा अर्को ब्लक कार्यान्वयन भएमा, यसले म्याग्लेन र j-i + १ बिच ठूलो नो दिन्छ र max लाई म्याग्लेनमा फर्काउँछ।

j = ०

एर [j] ० लाई बराबर, त्यसपछि शुन्य_क +्ग ++, को मतलब शून्य_गणना = १

र यसले लूपलाई पुनरावृत्तिकै राख्दछ जब सम्म सबै सर्तहरू विफल हुँदैनन्।

र maxlen 6 को रूपमा फर्काउनुहोस्।

कार्यान्वयन

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

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

समय जटिलता

O (N * N) जहाँ N दिइएको एर्रेको साइज हो।

ठाउँ जटिलता

O (१) किनकि हामी यहाँ कुनै अतिरिक्त ठाउँ प्रयोग गर्दैनौं।

संदर्भ