यदि दिइएको एर्रेमा एक अर्काबाट के दूरी भित्र नक्कल तत्वहरू छन् कि छैन जाँच गर्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन Avalara Citadel फ्रीचार्ज हैकरर्यांक Snapchat स्नैपडल
एरे हैश

समस्या "यदि दिइएको एर्रेले एक अर्काबाट के दूरी भित्र डुप्लीकेट एलिमेन्टहरू समावेश गर्दछ जाँच गर्नुहोस्" भन्छ कि हामीले k को दायरा भित्र नक्कल गरिएको एर्रेमा नक्कलहरू जाँच गर्नु पर्छ। यहाँ k को मान दिइएको array भन्दा सानो छ।

यदि दिइएको एर्रेमा एक अर्काबाट के दूरी भित्र नक्कल तत्वहरू छन् कि छैन जाँच गर्नुहोस्

उदाहरण

K = 3   arr[] = {1, 2, 3, 4, 5, 2, 1}
False
K = 2   arr[] = {3, 4, 3, 1, 1, 2, 6}
True

स्पष्टीकरण

हामीसँग यो समस्या समाधान गर्न दुई तरिकाहरू छन्। सरल एउटा भनेको दुई लूपहरू चलाउनु हो जसमा पहिलो लूपले प्रत्येक तत्वलाई दोस्रो लूप 'इनर लूप' को लागी शुरुवात गर्ने तत्वको रूपमा छान्छ। त्यस पछि, दोस्रो लूपले सुरूवात तत्त्वलाई 'k' को दायरा भित्रका सबै तत्वहरूसँग तुलना गर्नेछ। तर यो समाधान त्यति कुशल छैन कि यसले O (k * n) समयको जटिलता लिन्छ।

तर हामीसँग अर्को थप कुशल विधि छ जुन समस्या समाधान गर्न सक्दछ ऊ) समय जटिलता भनिन्छ हसिhing। ह्याशि method विधिमा, हामी एर्रेको सबै एलिमेन्टहरू ट्रान्सभर्स गर्नेछौं र हामी यो एलिमेन्ट उपस्थित छ कि छैन भनेर जाँच गर्नेछौं। यदि तत्व त्यहाँ छ भने हामी फर्कनेछौं 'ट्रु।' अन्यथा हामी यसलाई ह्यासमा थप्नेछौं र एर [ik] एलिमेन्ट ह्यासबाट हटाउनेछौं यदि 'i' 'k' भन्दा ठूलो वा बराबर छ भने।

एल्गोरिथ्म जाँच गर्न कि यदि दिइएको एर्रेमा एक अर्काबाट के दूरी भित्र नक्कल तत्त्वहरू छन्

  1. पहिले, खाली सिर्जना गर्नुहोस् ह्याश सेट जसमा हामी एर्रेको एलिमेन्ट स्टोर गर्नेछौं।
  2. एर्रेको सबै एलिमेन्टहरू बायाँ देखि दायाँ ट्रान्स गर्नुहोस्।
  3. यदि तत्त्व ह्यासमा छ वा छैन जाँच गर्नुहोस्।
    • यदि त्यहाँ छ भने फर्कनुहोस् "सत्य।"
    • अन्य तत्वमा ह्यासमा थप गर्नुहोस्।
  4. त्यस पछि एर [ik] एलिमेन्ट ह्यासबाट हटाउनुहोस् यदि 'I' ठूलो वा 'k' बराबर छ।

 

हामीसँग एर्रे छ [एर [] 'यसमा केही एलिमेन्ट सहित र एउटा मान k जो सीमा हो जुन हामीले डुप्लिकेटहरू पत्ता लगाउनु पर्ने हुन्छ यदि कुनै छ भने ह्याश सेट प्रयोग गर्नेछौं जसमा एलिमेन्ट्स भण्डार गर्न पहिले हामी एलिमेन्टहरू थप्नेछौं। हाम्रो ह्यासमा एर्रे एक एक गरी सेट गर्छ यदि एलिमेन्ट पहिले नै ह्यास सेटमा छ भने यो साँचो हुन्छ र लूप तोड्छ अन्यथा यसले सेटमा एलिमेन्टहरू निरन्तर घुसाउँदछ र एर [ik] एलिमेन्ट सेटबाट हटाउँदछ।

कोड

C ++ कोड जाँच गर्नको लागि यदि दिइएको एर्रेमा एक अर्काबाट के दूरी भित्र नक्कल तत्त्वहरू छन् भने

#include<iostream>
#include<unordered_set>
using namespace std;

bool Check_Duplicates(int a[], int n, int k)
{

    unordered_set<int> D_set;

    for (int i = 0; i < n; i++)
    {
        if (D_set.find(a[i]) != D_set.end())
            return true;

        D_set.insert(a[i]);
        if (i >= k)
            D_set.erase(a[i-k]);
    }
    return false;
}

int main ()
{
    int a[] = {1, 2, 3, 4, 1};
    int k = 5;
    cout << ((Check_Duplicates(a, 5, k)) ? "Yes" : "No");
}
Yes

जाभा कोड जाँच गर्नको लागि यदि दिइएको एर्रेमा एक अर्काबाट के दूरी भित्र नक्कल तत्त्वहरू छन् कि भनेर जाँच गर्न

import java.util.*;
class D_Class
{
    static boolean Check_Duplicates(int a[], int k)
    {

        HashSet<Integer> D_set = new HashSet<>();

        for (int i=0; i<a.length; i++)
        {
            if (D_set.contains(a[i]))
                return true;

            D_set.add(a[i]);
            if (i >= k)
                D_set.remove(a[i-k]);
        }
        return false;
    }

    public static void main (String[] args)
    {
        int a[] = {1, 2, 3, 4, 1};
        int k = 5;

        if (Check_Duplicates(a, k))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
Yes

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

समय जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। ह्याश सेट प्रयोग गर्नाले रेखामा समस्या समाधान गर्न अनुमति दिँदछ। ह्यास सेट प्रयोग गर्दा खोजी गर्न, मेटाउन र कुशलतापूर्वक डेटा घुसाउनको क्षमता बढाउँछ।

ठाउँ जटिलता

ठिक छ) जहाँ "K" विन्डोमा एलिमेन्ट्सको संख्या हो जुन हेर्नु आवश्यक पर्दछ।