के डिस्टिक्ट नंबरों के साथ सबसे छोटा सबर्रे  


कठिनाई स्तर कठिन
में अक्सर पूछा वीरांगना गूगल
ऐरे हैश फिसलने वाली खिडकी दो सूचक

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

उदाहरण  

इनपुट:

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

कश्मीर = 3

आउटपुट:

2, 4

स्पष्टीकरण:

{2, 3, 4} 2 से शुरू होने वाला सबसे छोटा उप-सरणी हैnd सूचकांक ४th k अर्थात 3 अलग तत्वों के साथ सूचकांक।

इनपुट:

{2, 5, 6, 7}

कश्मीर = 2

आउटपुट:

2, 3

स्पष्टीकरण:

{2, 5} दूसरा सबसे छोटा उप-सरणी है, जो 2 इंडेक्स से 3 के इंडेक्स से शुरू होता है।

कलन विधि  

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

व्याख्या  

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

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

सरणी के आघात के बाद, यदि बाईं ओर का सूचक 0 और दाईं ओर का सूचक n पाया जाता है, तो इसका मतलब है कि यह एक अमान्य k है। एल्स ने लेफ्ट और राइट साइड पॉइंटर के मूल्य को प्रिंट किया, जो कि शुरुआती सबसे छोटे उप-सरणी का एंड पॉइंट एंड होगा।

यह भी देखें
वैध सुडोकू

कार्यान्वयन  

C डिस्टिक्ट नंबरों के साथ सबसे छोटी सबर्रे के लिए C ++ प्रोग्राम # शामिल हैं

#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

के डिस्टिक्ट नंबरों के साथ सबसे छोटे सबर्रे के लिए जावा प्रोग्राम

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" सरणी में तत्वों की संख्या है।