०s र १ हरूको समान संख्याको साथ सब भन्दा ठूलो सबभ्रे


कठिनाई तह मध्यम
बारम्बार सोधिन्छ अमेजन Coursera ग्रेऑरेंज MakeMyTrip मोर्गन स्टेनले पेटम Synopsys टाइम्स इन्टरनेट
एरे हैश

तपाईंलाई पूर्णांकको एक एरे दिइन्छ। पूर्णांकहरू ० र १ मात्र इनपुट एर्रेमा हुन्छन्। समस्या कथनले सब भन्दा ठूलो सब-एरे पत्ता लगाउन सोध्दछ जुन ० र १ को बराबर गणना हुन सक्छ।

उदाहरणका

arr[]={0,1,0,1,0,1,1,1}
0 to 5 (total 6 elements)

स्पष्टीकरण

एर्रे स्थिति ० देखि। सम्म त्यहाँ ० सेकेन्ड १ को बराबर संख्या थियो

० से गणना 3

० से गणना ⇒ 3

र यो सब भन्दा ठूलो उप-एर्रे हो जुन ०s र १s बराबर हो।

0s र 1 हरूको समान संख्याको साथ ठूला सबबर्रे फेला पार्न एल्गोरिदम

  1. घोषणा गर्नुहोस् हशम्याप.
  2. सेट sum, अधिकतम लम्बाई, startIndex ० र अन्त्य सूचकांक to -1।
  3. एर्रे पार गर्नुहोस् र एर्रेको प्रत्येक एलिमेन्ट -१ लाई अपडेट गर्नुहोस् यदि यो ० बराबर छ।
  4. ० देखि n-१ सम्म लूप सुरू गर्नुहोस् (एन एर्रेको लम्बाई हो)।
    1. अररको प्रत्येक मान थप्नुहोस् [i] योगफल।
    2. यदि योगफल ० को बराबर हो भने जाँच गर्नुहोस्, ठीक भए,
      1. त्यसपछि अपडेट गर्नुहोस् अधिकतम लम्बाई जस्तो i + १, र अन्त्य सूचकांक जस्तो म।
    3. यदि नक्शाले यसमा जोड + n समावेश गर्दछ भने, जाँच गर्नुहोस्।
      1. तब अधिकतम लम्बाइको मान अपडेट गर्नुहोस् i - नक्सा (योग + n) नक्शाबाट र अन्त्य I सूचक I को रूपमा।
    4. अन्यले त्यो योग + n नक्शामा राख्दछ।
  5. EndingIndex - maxLength + १ र endingIndex प्रिन्ट गर्नुहोस्।

स्पष्टीकरण

एर्रे दिइयो र हामीलाई ०s र १ हरूको समान संख्याको साथ सब भन्दा ठूलो सब-एरे पत्ता लगाउन सोधिन्छ। उप-एर्रेको दायरा फेला पार्नुहोस् ता कि यो सब उप-एर्रे को सबै लम्बाइ बीच सब भन्दा ठूलो हुनु पर्छ जसले बराबर संख्या ० र १ राख्छ। हामी यो प्रयोग गर्दैछौं हशम्याप भण्डारण को लागी पूर्णांक यसमा मानहरू। ह्याशिंग एक कुशल दृष्टिकोण र राम्रो समय जटिलता प्रदान गर्दछ। मानहरू लिनुहोस् sum, अधिकतम लम्बाई 0 को रूपमा हामी यसलाई कोडमा एकै साथ अपडेट गर्न जाँदैछौं। हामीसँग अन्डीइन्डि called भनिने एक चल हुन्छ, यसले दायराको अन्तिम बिन्दुको मान राख्छ जहाँ सब-एरे समाप्तको दायराको अधिकतम लम्बाइ हुनुपर्दछ।

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

हामी एउटा एर्रेमा हरेक मान जोड्न जाँदैछौं, र यो ० बराबर छ कि छैन पत्ता लगाउँछ, यदि बराबर मात्र एर्रेको अधिकतम लम्बाइ अपडेट गर्दछ र एरेको अन्त्य अन्त्य सूचकांक। हामी मानचित्रलाई जोड्न गइरहेका छौं यदि यो पहिले नै अवस्थित छैन भने, र यदि यो अवस्थित छ भने केहि सर्तहरू जाँच्नुहोस् तब म्याक्सलिन्थे र अन्तीइन्डिडेक्सको मान अपडेट गर्नुहोस्। EndingIndex प्रिन्ट गर्नुहोस् - दायराको सुरूवात बिन्दुको रूपमा अधिकतम + १ र दायराको अन्त्य बिन्दुको रूपमा endingIndex।

०s र १ हरूको समान संख्याको साथ सब भन्दा ठूलो सबभ्रे

कोड

C ++ कोड ०s र १ हरूको समान संख्याको साथ ठूलो सबभर्रे फेला पार्न

#include<iostream>
#include<unordered_map>

using namespace std;

int getLargestSubA(int arr[], int n)
{
    unordered_map<int, int> MAP;

    int sum = 0;
    int maxLength = 0;
    int endingIndex = -1;

    for (int i = 0; i < n; i++)
        arr[i] = (arr[i] == 0) ? -1 : 1;

    for (int i = 0; i < n; i++)
    {
        sum += arr[i];
        if (sum == 0)
        {
            maxLength = i + 1;
            endingIndex = i;
        }
        if (MAP.find(sum + n) != MAP.end())
        {
            if (maxLength < i - MAP[sum + n])
            {
                maxLength = i - MAP[sum + n];
                endingIndex = i;
            }
        }
        else
            MAP[sum + n] = i;
    }
    cout<<endingIndex - maxLength + 1 <<" to " <<endingIndex;

    return maxLength;
}

int main()
{
    int arr[] = { 0,1,0,1,0,1,1,1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    getLargestSubA(arr, n);
    return 0;
}
0 to 5

जाभामा कार्यान्वयन ० र १ को बराबर संख्याको साथ ठूला सबबर्रे फेला पार्न

import java.util.HashMap;

class LargestSubArrayWithEqual01
{
    public static int getLargestSubA(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        int sum = 0;

        int maxLength = 0;
        int endingIndex = -1;

        for (int i = 0; i < n; i++)
        {
            arr[i] = (arr[i] == 0) ? -1 : 1;
        }

        for (int i = 0; i < n; i++)
        {
            sum += arr[i];
            if (sum == 0)
            {
                maxLength = i + 1;
                endingIndex = i;
            }
            if (MAP.containsKey(sum + n))
            {
                if (maxLength < i - MAP.get(sum + n))
                {
                    maxLength = i - MAP.get(sum + n);
                    endingIndex = i;
                }
            }
            else
                MAP.put(sum + n, i);

        }
        int end = endingIndex - maxLength + 1;
        System.out.println(end + " to " + endingIndex);

        return maxLength;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {0,1,0,1,0,1,1,1};
        int n = arr.length;

        getLargestSubA(arr, n);
    }
}
0 to 5

जटिलता विश्लेषण

समय जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। यहाँ हामी यस समस्यालाई ओ (एन) मा समाधान गर्न सक्छौं किनभने हामीले ह्यासम्याप प्रयोग गरेका छौं। किनभने ह्यासम्यापले ओ (१) समय जटिलतामा तत्व घुसाउन, मेटाउन वा परिमार्जन गर्न सक्दछ।

ठाउँ जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। भएकोले एलिमेन्ट्सको संख्या जुन ह्यासम्यापमा सबैभन्दा खराब केसमा सम्मिलित हुन्छ अधिकतम एन हो। यो लाइनर अन्तरिक्ष जटिलता हासिल गरियो।