मिल्दो तत्वहरूको साथ सबैभन्दा ठूलो सबभर्रेको लम्बाई


कठिनाई तह मध्यम
बारम्बार सोधिन्छ एडोब अमेजन ब्लूमबर्ग सिस्को karat मोनोटाइप समाधानहरू पेटम PayU पब्लिसिस सेपिएन्ट SAP ल्याबहरू
एरे हैश

समस्या "सान्दर्भिक तत्त्वहरूको साथ सब भन्दा ठूलो सबभर्रेको लम्बाई" ले तपाईंलाई एक दिइन्छ भनेर बताउँछ पूर्णांक array। समस्या कथन को लागी सबैभन्दा लामो मिल्दो उप-एर्रे को लम्बाइ पत्ता लगाउन को लागी सोध्नुहोस् जुन तत्वहरुको अनुक्रम मा क्रमबद्ध गर्न सकिन्छ (निरन्तर, या त आरोही वा अवरोही)। एर्रेमा नम्बरहरू धेरै पटक देखा पर्न सक्छ।

उदाहरणका

मिल्दो तत्वहरूको साथ सबैभन्दा ठूलो सबभर्रेको लम्बाई

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

स्पष्टीकरण

० सेमी सूचकबाट तेस्रो सूचकांकमा सुरू हुने संख्या १०, १२, १ 0, ११ समावेश गर्दछ जुन १०, ११, १२, १ which तरिकामा व्यवस्थित गर्न सकिन्छ जसको लम्बाई 3 हुन्छ।

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

स्पष्टीकरण

पहिलो अनुक्रमणिकाबाट तेस्रो सूचकांकमा सुरू हुने संख्यामा १,,, २ समावेश हुन्छन् जुन १, २, manner तरिकामा मिलाउन सकिन्छ जसको लम्बाई 1 हुन्छ।

अल्गोरिदम

  1. सेट अधिकतम लम्बाई 1 मा।
  2. एउटा लूप खोल्नुहोस्, i = ०, जबकि i <l -0,
    1. घोषणा गर्नुहोस् सेट र एर थप्नुहोस् [i] सेट मा।
    2. को मान सेट गर्नुहोस् म्याक्सलेनminlen एर गर्न [i]।
    3. लूप खोल्नुहोस्, j = i + १ बाट सुरू गरेर, जबकि <<l,
      1. सेटमा अरर [j] को मान छ कि छैन जाँच गर्नुहोस्।
        1. यदि सहि छ भने, ब्रेक गर्नुहोस्।
        2. अन्य,
          1. एरर [j] सेट मा जोड्नुहोस्।
          2. मिलन र एरर [j] बीचको न्यूनतम फेला पार्नुहोस् र मिलनमा भण्डार गर्नुहोस्।
          3. म्याक्सलेन र एरर [j] को बीचमा अधिकतम पत्ता लगाउनुहोस् र यसलाई म्याक्सलेनमा भण्डार गर्नुहोस्।
          4. जाँच गर्नुहोस् कि अधिकतम मिनेट = = j - i
            1. यदि सहि छ भने maxLength र अधिकतम- minlen बीच अधिकतम फेला पार्नुहोस् र यसलाई maxLength मा भण्डार गर्नुहोस्।
  3. फिर्ता maxLength।

स्पष्टीकरण

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

हामी एक उदाहरण विचार गरौं:

उदाहरणका

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

हामी एउटा लूप खोले पछि सेट प्रयोग गर्नेछौं र नम्बरहरू जोड्नेछौं, एक पटकमा एक, र म्याक्सलेन र मिलनको मान सेट गर्नेछ [i]। त्यसो भए हालको एलिमेन्ट भन्दा अगाडि नेस्ट गरिएको लूप खोल्नुहोस्, किनकि हामीले हालको एलिमेन्ट सेटमा राखिसकेका छौं। सेटमा एर [j] को मान छ कि छैन जाँच गर्नुहोस्, यदि एलिमेन्ट फेला पर्‍यो भने ब्रेक गर्नुहोस्। अन्यथा अररको मूल्य घुसाउनुहोस् [j] सेटमा र अधिकतम फेला पार्नुहोस् अधिकतम र एरर [j] बीचमा, र न्यूनतम पनि मिल्न र एर [j] र यसलाई भण्डार गर्नुहोस् क्रमशः जाँच गर्नुहोस् कि अधिकतम मिनेट जी बराबर हो, तब अधिकतमको मूल्य अपडेट गर्नुहोस्।

अधिकतम लम्बाई = १।

i = 0, mySet = {10}, minlen = 10, अधिकतम = १०

j = i + १ = १, यदि माईसेटमा १२ छ भने गलत छ,

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

j = 2, यदि मायसेटसँग १ 13 छ भने गलत छ,

त्यसो भए माईसेटमा १ in सम्मिलित गर्नुहोस् र अधिकतम १ and र १२ फेला पार्नुहोस् र १ store लाई म्याक्सलेनमा र १० लाई मिलनमा हेर्नुहोस् र जाँच्नुहोस् कि म्याक्सलेन-मिलेन जे बराबर छ - म गलत हो।

j = 3, यदि मायसेटसँग १ 11 छ भने गलत छ,

त्यसो भए मायसेटमा ११ सम्मिलित गर्नुहोस् र ११ र १० अधिकतम फेला पार्नुहोस् र १ 11 लाई म्याक्सलेन र १० लाई मिलनमा भण्डार गर्नुहोस् र जाँच्नुहोस् कि म्याक्सलेन-मिलेन जे बराबर छ - म अब सत्य हुँ किनकि १-11-१० बराबर 10-० छ। त्यसैले अधिकतम म्याक्सलेन्गथ र म्याक्सलेन-मिलेन + १ अधिकतम (१, १-13-१० + १) पत्ता लगाएर अधिकतम अपडेट गर्नुहोस् र यो and र the पाइन सकिन्छ अधिकतम लम्बाईमा भण्डार गरिएको छ र यसले एर्रेमा ट्र्याभिंग गरिरहनेछ र सेट गर्नुहोस् जब सम्म यसले यो मिल्दो उप-एर्रेको भन्दा लामो लम्बाइ पाउँदैन।

आउटपुट: १।

कोड

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

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

समय जटिलता

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

ठाउँ जटिलता

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