के डिस्टिंक्ट नम्बरहरूको साथ सब भन्दा सानो सुवाराय  


कठिनाई तह हार्ड
बारम्बार सोधिन्छ अमेजन गुगल
एरे हैश स्लाइडि Wind विन्डो दुई पोइन्टर

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

उदाहरणका  

इनपुट:

{1, 2, 2, 3, 4, 5, 5}

k = 3

उत्पादन:

2, 4

व्याख्या:

From २,,,} 2 सब भन्दा सानो उप-एर्रे २ बाट शुरू भयोnd 4 मा सूचकांकth k को साथ सूचकांक, distin भिन्न तत्वहरू।

इनपुट:

{2, 5, 6, 7}

k = 2

उत्पादन:

2, 3

व्याख्या:

Index २,} k सब भन्दा सानो उप-एरे २ सेमी सूचकांक तेस्रो अनुक्रमणिकाबाट के.ई., २ भिन्न तत्वहरूको साथ सुरू हुन्छ।

अल्गोरिदम  

  1. ० र बायाँ छेउ र दायाँ पट्टी सूचक -१ मा फरक तत्व सेट गर्नुहोस्।
  2. एर्रेबाट पार गर्नुहोस्,
  3. १ द्वारा दायाँपट्टी बढाउँदै, यदि कुनै फरक तत्वहरू मध्ये कुनै दिइएको संख्या k भन्दा कम छ भने,
  4. त्यसपछि काउन्ट बढाउनुहोस् र एरे एलिमेन्टको फ्रिक्वेन्सी नक्सा.
  5. यदि फरक तत्वहरू दिइएको संख्या k सँग बराबर छ र बनिएको लम्बाई अघिल्लो अपडेट गरिएको लम्बाइ भन्दा सानो छ भने बाँया र दायाँ पोइन्ट पोइन्टर्स र ब्रेक।
  6. यदि फरक तत्वहरूको संख्या k भन्दा कम पाए भने ब्रेक गर्नुहोस्।
  7. जाँच गर्नुहोस् यदि फरक तत्वहरूको संख्या k को बराबर भयो भने दायाँ पोइन्ट पोइन्टर्स बढाउनुहोस्।
  8. यदि फरक तत्वहरू दिइएको संख्या k सँग बराबर छ र बनिएको लम्बाई अघिल्लो अपडेट गरिएको लम्बाइ भन्दा सानो छ भने बाँया र दायाँ पोइन्ट पोइन्टर्स र ब्रेक।
  9. जाँच गर्नुहोस् कि यदि तत्वको फ्रिक्वेन्सी १ पाइएको छ भने नक्शाबाट त्यो तत्व हटाउनुहोस्, अन्यथा त्यो तत्वको फ्रिक्वेन्सीको गणना कम गर्नुहोस्।
  10. यदि बायाँपट्टि सूचक ० र दायाँ पट्टि n बराबर हुन पाएमा, यसको मतलब यो अवैध हो।
  11. अन्यथा, बाँया साइड र दायाँ पट्टी मान प्रिन्ट गर्नुहोस्।
पनि हेर्नुहोस्
सापेक्षिक क्रमबद्ध एर्रे लेटकोड समाधान

स्पष्टीकरण  

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

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

एर्रेको ट्रान्सभर्ल पछि, यदि बायाँपट्टि सूचक ० र n को दायाँतिर सूचक पाइन्छ भने, यसको मतलब यो एक अवैध k हो। अन्यथा बाँया र दायाँ पोइन्ट सूचकको मान प्रिन्ट गर्नुहोस् जुन समावेशी रूपमा साना सब-एरेको सुरूवात बिन्दु र अन्त्य बिन्दु हुनेछ।

पनि हेर्नुहोस्
मान्य सुडोकु

कार्यान्वयन  

सी ++ प्रोग्राम सबैभन्दा सानो सुब्ब्रेको लागि के डिस्टिन्ट नम्बरहरू सहित # समावेश गर्दछ

#include<map>

using namespace std;

void getSmallestSubarray(int arr[], int n, int k)
{
    int left = 0, right = n;
    int j = -1;
    map<int, int> MAP;
    for (int i=0; i<n; i++)
    {
        while (j < n)
        {
            j++;
            if (MAP.size() < k)
                MAP[arr[j]]++;

            if (MAP.size() == k && ((right - left) >= (j - i)))
            {
                left = i;
                right = j;
                break;
            }

        }
        if (MAP.size() < k)
            break;

        while (MAP.size() == k)
        {
            if (MAP[arr[i]] == 1)
                MAP.erase(arr[i]);
            else
                MAP[arr[i]]--;

            i++;

            if (MAP.size() == k && (right - left) >= (j - i))
            {
                left = i;
                right = j;
            }
        }
        if (MAP[arr[i]] == 1)
            MAP.erase(arr[i]);
        else
            MAP[arr[i]]--;
    }
    if (left == 0 && right == n)
        cout << "Invalid k" << endl;
    else
        cout << left << " " << right;
}
int main()
{
    int arr[] = {1, 2, 2, 3, 4, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    getSmallestSubarray(arr, n, k);
    return 0;
}
2 4

K डिस्टिन्क्ट नम्बरहरूको साथ सब भन्दा सानो सुब्र्रेका लागि जाभा प्रोग्राम

import java.util.HashMap;
import java.util.Map;
class smallestSubArray
{
    public static void getSmallestSubarray(int arr[], int n, int k)
    {
        int left = 0, right = n;
        int j = -1;
        HashMap<Integer, Integer> MAP=new HashMap<>();
        for (int i=0; i<n; i++)
        {
            while (j < n-1)
            {
                j++;
                if (MAP.size() < k)
                {

                    if(MAP.containsKey( arr[j] ))
                        MAP.put( arr[j], MAP.get( arr[j] ) + 1 );
                    else
                        MAP.put(arr[j],1);
                }

                if (MAP.size() == k && ((right - left) >= (j - i)))
                {
                    left = i;
                    right = j;
                    break;
                }
            }
            if (MAP.size() < k)
                break;

            while (MAP.size() == k)
            {
                if (MAP.get(arr[i]) == 1)
                    MAP.remove(arr[i]);
                else
                    MAP.put(arr[i], MAP.get(arr[i])-1);

                i++;

                if (MAP.size() == k && (right - left) >= (j - i))
                {
                    left = i;
                    right = j;
                }
            }
            if (MAP.get(arr[i]) == 1)
                MAP.remove(arr[i]);
            else
                MAP.put(arr[i], MAP.get(arr[i])-1);
        }
        if (left == 0 && right == n)
            System.out.println("Invalid k");
        else
            System.out.println(left+" "+right);
    }
    public static void main(String [] args)
    {
        int arr[] = {1, 2, 2, 3, 4, 5, 5};
        int n = arr.length;
        int k = 3;
        getSmallestSubarray(arr, n, k);

    }
}
2 4

के डिस्टिंक्ट नम्बरहरूको साथ सब भन्दा सानो सुब्र्रेका लागि जटिलता विश्लेषण  

समय जटिलता

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

पनि हेर्नुहोस्
जोडीहरू गणना गर्नुहोस् जसको उत्पादहरू एर्रेमा अवस्थित छन्

ठाउँ जटिलता

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