1s को गणना भन्दा अधिक 0s गणनाको सब भन्दा लामो सुभ्रे


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एक्सेंचर अमेजन डे श Samsung
एरे हैश

हामीले एउटा दिएका छौं array पूर्णांकको। एर्रेमा १ र ० मात्र समावेश छ। समस्या कथनले सब भन्दा लामो सब-एरेको लम्बाइ पत्ता लगाउन सोध्छ जुन १ को अ of्कको मात्रा भएको उप-एरेमा ० को गणनाको तुलनामा केवल एक बढी हो।

उदाहरणका

इनपुट:

एर [] = {२,1,0,1,1,0,0,0,१०,१,१२}

उत्पादन:

5

व्याख्या:

० देखि index सूचकांकमा, {१, ०, १, १, ०}, त्यहाँ तीन छन् १ र दुई ० को। १ को ० भन्दा बढि एक गणना।

इनपुट:

एर [] = {२,1,0,1,0,0,१०,१,१२}

उत्पादन:

3

व्याख्या:

० देखि २ सूचकांक, {१, ०, १}, त्यहाँ दुई १ र १ ० छ। १ को ० भन्दा बढि एक गणना।

अल्गोरिदम

  1. नक्शा घोषणा गर्नुहोस्।
  2. योगफल र आउटपुटLength ० मा सेट गर्नुहोस्।
  3. एरे ट्राभर्स गर्नुहोस्, जबकि i = ० लाई i <n।
    1. यदि एर [i] ० बराबर छ भने जाँच गर्नुहोस् यदि सही हो भने जोडमा -१ थप्नुहोस्।
    2. अन्य जोडमा +१ थप्नुहोस्।
    3. जाँच गर्नुहोस् यदि योग बराबर छ १ मा, त्यसपछि आउटपुटलिन्टको मान १ बढाउनुहोस्।
    4. अन्य, यदि नक्साले जोड समावेश गर्दैन भने जाँच गर्नुहोस् यदि सही हो भने योगको साथ i को मान र हालको मान राख्दछ।
    5. यदि नक्शामा (योग -१) समावेश छ भने जाँच गर्नुहोस्।
    6. यदि आउटपुटलिन्ग आई-अनुक्रमणिका भन्दा कम हो (नक्सामा योगफलको मान)।
      1. यदि सहि छ भने, तब आउटपुटलिन्ग आई-इन्डेक्समा अपडेट गर्नुहोस्।
  4. फिर्ता आउटपुट लम्बाई।

स्पष्टीकरण

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

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

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

कार्यान्वयन

सी ++ प्रोग्राम सबैभन्दा लामो सुबर्रेको लागि १ एसको गणना ० सेकेन्डको गणना भन्दा बढि छ

#include <iostream>
#include<unordered_map>

using namespace std;

int getLongestLen(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int sum = 0, outputLength= 0;

    for (int i = 0; i < n; i++)
    {

        if(arr[i] == 0)
            sum += -1;
        else
            sum += 1;


        if (sum == 1)
        {
            outputLength = i + 1;
        }
        else if (MAP.find(sum) == MAP.end())
        {
            MAP[sum] = i;
        }

        if (MAP.find(sum - 1) != MAP.end())
        {
            if (outputLength < (i - MAP[sum - 1]))
                outputLength = i - MAP[sum - 1];
        }
    }
    return outputLength;
}
int main()
{
    int arr[] = {1,0,1,1,0,0,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the longest Sub-Array : "<<getLongestLen(arr, n);
    return 0;
}
Length of the longest Sub-Array : 5

सबै भन्दा लामो सुब्र्रेको लागि जाभा प्रोग्राम ० एसको गणना भन्दा १s एक गणना गर्दछ

import java.util.HashMap;

class longestSubArray01
{
    public static int getLongestLen(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>();
        int sum = 0, outputLength = 0;

        for (int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
                sum += -1;
            else
                sum += 1;

            if (sum == 1)
                outputLength = i + 1;
            else if (!MAP.containsKey(sum))
                MAP. put(sum, i);


            if (MAP.containsKey(sum - 1))
            {
                if (outputLength < (i - MAP.get(sum - 1)))
                    outputLength = i - MAP.get(sum - 1);
            }
        }
        return outputLength;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,0,1,1,0,0,0};
        int n = arr.length;
        System.out.println("Length of the longest Sub-Array : " +getLongestLen(arr, n));
    }
}
Length of the longest Sub-Array : 5

सब भन्दा लामो सुब्र्रेको लागि जटिलता विश्लेषण ० एसको गणना भन्दा १s एकको गणना छ

समय जटिलता

ऊ) जहाँ "N"  एर्रेमा एलिमेन्ट्सको संख्या हो।

ठाउँ जटिलता

ऊ) जहाँ "N"  एर्रेमा एलिमेन्ट्सको संख्या हो।