सन्निहित तत्वों के साथ सबसे बड़े सबरे की लंबाई


कठिनाई स्तर मध्यम
में अक्सर पूछा एडोब वीरांगना ब्लूमबर्ग सिस्को खरात मोनोटाइप समाधान Paytm PayU पब्लिसिस सैपिएंट एसएपी लैब्स
ऐरे हैश

समस्या "सन्निहित तत्वों के साथ सबसे बड़ी सबरे की लंबाई" बताती है कि आपको ए पूर्णांक सरणी। समस्या कथन सबसे लंबे समय तक सन्निहित उप-सरणी की लंबाई का पता लगाने के लिए कहता है जिसमें तत्वों को एक अनुक्रम में व्यवस्थित किया जा सकता है (निरंतर, या तो आरोही या अवरोही)। सरणी में संख्या कई बार हो सकती है।

उदाहरण

सन्निहित तत्वों के साथ सबसे बड़े सबरे की लंबाई

arr[] = {10, 12, 13, 11, 8, 10, 11, 10}
4

व्याख्या

0 वें इंडेक्स से 3 डी इंडेक्स पर शुरू होने वाले नंबर में 10, 12, 13, 11 नंबर होते हैं जिन्हें 10, 11, 12, 13 तरीके से व्यवस्थित किया जा सकता है, जिनमें से लंबाई 4 हो जाती है।

arr[] = {1, 1, 3, 2, 8, 4, 8, 10}
3

व्याख्या

पहली अनुक्रमणिका से 1 तर्जनी तक की संख्या में 3, 1, 3 संख्याएँ होती हैं जिन्हें 2, 1, 2 तरीके से व्यवस्थित किया जा सकता है, जिनमें से लंबाई 3 है।

कलन विधि

  1. सेट अधिकतम लंबाई 1 लिए.
  2. एक लूप खोलें, i = 0, जबकि मैं <l -1,
    1. डिक्लेयर ए सेट और सेट में गिरफ्तारी [i] जोड़ें।
    2. का मान निर्धारित करें अधिकतम और मीनल गिरफ्तार करने के लिए [i]
    3. J = i + 1 से शुरू करते हुए एक लूप खोलें, जबकि j <l,
      1. जाँच करें कि क्या सेट में गिरफ्तारी का मूल्य है [j],
        1. अगर सच है, तो तोड़ो।
        2. अन्य,
          1. सेट में गिरफ्तारी [जे] जोड़ें।
          2. मिनलेन और गिरफ्तार [जे] के बीच न्यूनतम का पता लगाएं और इसे मिनीलेन में संग्रहीत करें।
          3. मैक्सलेन और गिरफ्तार [जे] के बीच अधिकतम का पता लगाएं और इसे अधिकतम करने के लिए स्टोर करें।
          4. जांचें कि क्या अधिकतम-मिन = = जे - आई
            1. अगर सच है तो अधिकतम और अधिकतम- minlen +1 के बीच अधिकतम का पता लगाएं और इसे maxLength पर स्टोर करें।
  3. अधिक से अधिक वापसी।

व्याख्या

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

चलिए, हम एक उदाहरण पर विचार करते हैं:

उदाहरण

Arr [] = {१०, १२, १३, ११, {, १०}

हम एक लूप खोलने के बाद एक सेट का उपयोग करेंगे और एक समय में एक, संख्या जोड़ेंगे, और गिरफ्तार करने के लिए अधिकतम और minlen का मान सेट करेंगे [i]। फिर वर्तमान तत्व के आगे एक तत्व से शुरू होने वाला नेस्टेड लूप खोलें, क्योंकि हमने पहले से ही सेट में वर्तमान तत्व डाला है। जांचें कि क्या सेट में गिरफ्तारी [j] का मूल्य है, यदि तत्व पाया जाता है, तो तोड़ दें। एल्स सेट में गिरफ्तारी [जे] के मूल्य को सम्मिलित करते हैं और अधिकतम और गिरफ्तार [जे] के बीच अधिकतम पता लगाते हैं, और न्यूनतम न्यूनतम और गिरफ्तारी [जे] के बीच भी रखते हैं और इसे क्रमशः अधिकतम और मिनीलेन में संग्रहीत करते हैं। जांचें कि क्या अधिकतम-मिन जी के बराबर है, तो अधिकतम मूल्य का अद्यतन करें।

अधिकतम गति = १।

i = 0, mySet = {10}, minlen = 10, maxlen = 10

j = i + 1 = 1, यदि mySet में 12 होंगे, गलत है,

इसलिए 12 mySet में डालें और अधिकतम 12 और 10 को खोजें और न्यूनतम 12 को अधिकतम और 10 को minlen में स्टोर करें और जांचें कि क्या maxlen-minlen j - i के बराबर है, लेकिन यह गलत है।

j = 2, अगर mySet में 13 होंगे, गलत है,

तो mySet में 13 डालें और 13 और 12 की अधिकतम ढूँढें और 13 को अधिकतम और 10 minlen में स्टोर करें और जांचें कि क्या maxlen-minlen j के बराबर है - i is false।

j = 3, अगर mySet में 11 होंगे, गलत है,

तो mySet में 11 डालें और 11 और 10 की अधिकतम ढूँढें और 13 को अधिकतम और 10 को minlen में संग्रहीत करें और जांचें कि क्या maxlen-minlen j के बराबर है - मैं अब सत्य हूं क्योंकि 13-10 3-0 के बराबर है। इसलिए अधिकतम अधिकतम गति और अधिकतम-मीनलेन + 1 अधिकतम (1, 13-10 + 1) का पता लगाकर अधिकतम गति को अपडेट करें और यह पता चला कि 4 और 4 अधिकतमभार में संग्रहीत है और यह सरणी को बनाए रखेगा और सेट जब तक यह सन्निहित उप-सरणी की तुलना में लंबी लंबाई पाता है।

आउटपुट: १

कोड

C ++ कोड सन्निहित तत्वों के साथ सबसे बड़े सबरे की लंबाई का पता लगाने के लिए

#include<set>
#include<iostream>

using namespace std;

int getLongestLength(int arr[], int l)
{
    int maxLength = 1;
    for (int i=0; i<l-1; i++)
    {
        set<int> mySet;
        mySet.insert(arr[i]);
        int minlen = arr[i], maxlen = arr[i];

        for (int j=i+1; j<l; j++)
        {
            if (mySet.find(arr[j]) != mySet.end())
                break;

            mySet.insert(arr[j]);
            minlen = min(minlen, arr[j]);
            maxlen = max(maxlen, arr[j]);

            if (maxlen - minlen == j - i)
                maxLength = max(maxLength, maxlen - minlen + 1);
        }
    }
    return maxLength;
}
int main ()
{
    int arr[] = {10, 12, 13, 11, 8, 10};
    int l = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the Longest contiguous Sub-Array is: " << getLongestLength(arr, l);
    return 0;
}
Length of the Longest contiguous Sub-Array is: 4

जावा कोड सन्निहित तत्वों के साथ सबसे बड़े सबरे की लंबाई का पता लगाने के लिए

import java.util.HashSet;

class largestSubArrayContiguousElements
{
    public static int getLongestLength(int arr[])
    {
        int l = arr.length;
        int maxLength = 1;

        for (int i=0; i< l-1; i++)
        {
            HashSet<Integer> mySet = new HashSet<>();
            mySet.add(arr[i]);

            int min = arr[i];

            int max = arr[i];

            for (int j=i+1; j<l; j++)
            {
                if (mySet.contains(arr[j]))
                    break;

                mySet.add(arr[j]);
                min = Math.min(min, arr[j]);
                max = Math.max(max, arr[j]);

                if (max-min == j-i)
                    maxLength = Math.max(maxLength, max-min+1);
            }
        }
        return maxLength;
    }
    public static void main (String[] args)
    {
        int arr[] = {10, 12, 13, 11, 8, 10};
        System.out.println("Length of the Longest contiguous SubArray is: "+getLongestLength(arr));
    }
}
Length of the Longest contiguous SubArray is: 4

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

समय जटिलता

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

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

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