सबसे लंबे सबर्रे में 1s की गणना 0 से अधिक की गिनती से अधिक है  


कठिनाई स्तर आसान
में अक्सर पूछा एक्सेंचर वीरांगना डीई शॉ सैमसंग
ऐरे हैश

हमने ए सरणी पूर्णांकों का। एक सरणी में केवल 1 और 0 होते हैं। समस्या कथन सबसे लंबे उप-ऐरे की लंबाई का पता लगाने के लिए कहता है, जिसमें 1 अंक की मात्रा केवल उप-सरणी में 0 की गिनती से एक अधिक है।

उदाहरण  

इनपुट:

arr [] = {1,0,1,1,0,0,0}

आउटपुट:

5

स्पष्टीकरण:

0 से 4 सूचकांक, {1, 0, 1, 1, 0} से, तीन हैं 1 का और दो 0 का। 1 के 0 की तुलना में सिर्फ एक और गिनती।

इनपुट:

arr [] = {1,0,1,0,0}

आउटपुट:

3

स्पष्टीकरण:

० से २ सूचकांक, {१, ०, १}, दो १ और एक ० हैं। 0 के 2 की तुलना में सिर्फ एक और गिनती।

कलन विधि  

  1. नक्शा घोषित करें।
  2. योग और आउटपुट को सेट करें।
  3. सरणी को पार करें, जबकि मैं = 0 से i <n।
    1. जाँच लें कि अगर गिरफ्तारी [i] 0 के बराबर है अगर सही है तो योग जोड़ दें।
    2. कुल योग +1 जोड़ने के लिए।
    3. जांचें कि क्या योग बराबर है 1 करने के लिए, फिर 1 से outputLength के मूल्य में वृद्धि।
    4. ठीक है, जांचें कि क्या किसी मानचित्र में योग नहीं है यदि सत्य है तो योग और वर्तमान मान को मैं जोड़ देता हूं जो राशि के साथ नक्शा है।
    5. जांचें कि क्या किसी मानचित्र में (योग -1) है।
    6. यदि outputLength आई-इंडेक्स (मानचित्र में योग के मूल्य) से कम है।
      1. यदि सही है, तो आउटपुट-लेवल को I-index में अपडेट करें।
  4. वापसी आउटपुट लंबाई।
यह भी देखें
एम रेंज के बाद बाइनरी सरणी संचालन को चालू करती है

व्याख्या  

हम घोषणा करेंगे नक्शा। उस नक्शे में, हम राशि के मूल्य और एक सूचकांक के वर्तमान मूल्य को संग्रहीत करने जा रहे हैं, अगर स्थिति संतुष्ट हो जाती है। दो चर ले लो और 0 पर सेट करें और outputLength को 0 पर सेट करें। सरणी को ट्रेस करते हुए, हम एक एरे के प्रत्येक तत्व को चुनेंगे, और जाँचेंगे कि क्या गिरफ्तारी [i] 0 के बराबर है, यदि यह बराबर पाया जाता है, तो हम जोड़ देंगे -1 को योग करने के लिए और इसे स्टोर करने के लिए, अन्यथा यदि हमें 0 नहीं मिला है, तो हम सकारात्मक 1 को जोड़कर जोड़ देंगे और इसे योग करने के लिए संग्रहीत करेंगे।

उस नकारात्मक 1 और सकारात्मक 1 के पीछे का कारण है, हम सभी 0 से -1 का दिखावा कर रहे हैं और उन्हें 1 के साथ जोड़ते हैं, इसलिए हमें हमेशा 0 मिलेगा। लेकिन हम सकारात्मक 1 राशि में जांच करेंगे, जो इंगित करता है कि हमारे पास एक अतिरिक्त 1 होगा तो 0 की गिनती।

मान लीजिए, हम 1, 0, 1 लेंगे, अगर हम 0 को -1 बता रहे हैं, तो हम पहले 0 नंबरों के साथ 2 प्राप्त करेंगे, और तीसरे नंबर के साथ, हम पा सकते हैं कि हमारी स्थिति पूरी हो गई है। हमें 1 के 0 का उप-सरणी मिला और 1 का 0 से एक अतिरिक्त गिनती के साथ। हम अपनी स्थिति को संतुष्ट करते हैं। इसीलिए हम देख रहे होंगे कि एल्गोरिथ्म के अगले चरण में योग 1 के बराबर है या नहीं, यह आउटपुटलैंथ की लंबाई को अद्यतन करेगा। आखिरी में, यदि कथन, यदि हमें नई आउटपुट लंबाई मिलती है, तो हमें वर्तमान आउटपुट के साथ पिछले एक को अपडेट करने की आवश्यकता है और हम आउटपुट लाइट को वापस कर देंगे।

यह भी देखें
डुप्लिकेट तत्व खोजें

कार्यान्वयन  

सबसे लंबे समय तक सबारे के लिए C ++ प्रोग्राम 1s की गणना के बाद 0s की गिनती से अधिक है

#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

सबसे लंबे सबर्रे के लिए जावा प्रोग्राम 1s की गणना 0 से अधिक की गिनती के साथ है

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

सबसे बड़ी सबर्रे के लिए जटिलता विश्लेषण 1 की गिनती की तुलना में 0s की गिनती से अधिक है  

समय जटिलता

पर) जहां "N"  सरणी में तत्वों की संख्या है।

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

पर) जहां "N"  सरणी में तत्वों की संख्या है।