जांचें कि क्या किसी दिए गए सरणी में एक दूसरे से k दूरी के भीतर डुप्लिकेट तत्व हैं


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना Avalara गढ़ स्वतंत्र प्रभार HackerRank Snapchat स्नैपडील
ऐरे हैश

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

जांचें कि क्या किसी दिए गए सरणी में एक दूसरे से k दूरी के भीतर डुप्लिकेट तत्व हैं

उदाहरण

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

व्याख्या

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

लेकिन हमारे पास एक और अधिक कुशल तरीका है जो समस्या को हल कर सकता है पर) समय जटिलता कहा जाता है हैशिंग। हैशिंग विधि में, हम सरणी के सभी तत्वों को पीछे छोड़ देंगे और हम जांचेंगे कि तत्व इसमें मौजूद है या नहीं। अगर तत्व वहां है तो हम 'ट्रू' को लौटा देंगे। वरना हम इसे हैश में जोड़ देंगे और हैश से '[ik] तत्व को हटा देंगे यदि' i '' k 'से अधिक या बराबर है।

यह जाँचने के लिए कि क्या किसी दिए गए सरणी में एक दूसरे से k दूरी के भीतर डुप्लिकेट तत्व हैं

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

 

हमारे पास इसमें कुछ तत्व के साथ एक 'अरेस्ट []] है और एक वैल्यू k है जो वह रेंज है जिसमें हमें डुप्लिकेट ढूंढना पड़ता है अगर कोई ऐसा है तो इसमें तत्वों को स्टोर करने के लिए हैश सेट का उपयोग करेंगे पहले हम तत्वों को जोड़ देंगे हमारे हैश में सरणी एक-एक करके सेट होती है यदि तत्व पहले से ही हैश सेट में है, तो यह सही लौटेगा और लूप को तोड़ देगा अन्यथा यह लगातार सेट में तत्वों को सम्मिलित करेगा और सेट से गिरफ्तार [ik] तत्व को हटा देगा।

कोड

C ++ कोड यह जांचने के लिए कि क्या दिए गए सरणी में एक दूसरे से k दूरी के भीतर डुप्लिकेट तत्व हैं

#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" सरणी में तत्वों की संख्या है। हैश सेट का उपयोग करने से रैखिक समय में समस्या को हल करने की अनुमति मिलती है। चूंकि हैश सेट का उपयोग करने से कुशलता से डेटा को खोजने, हटाने और डालने की क्षमता में वृद्धि होती है।

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

ठीक) जहां "क" खिड़की में तत्वों की संख्या है जिस पर ध्यान देने की आवश्यकता है।