दिलेल्या अ‍ॅरेमध्ये एकमेकांपासून के अंतरावर डुप्लिकेट घटक आहेत का ते तपासा


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन अवलारा किल्ला फ्रीचार्ज हॅकररँक Snapchat Snapdeal
अरे हॅश

“दिलेल्या अ‍ॅरेमध्ये एकमेकांपेक्षा के अंतरात डुप्लीकेट घटक आहेत की नाही ते तपासा” ही समस्या नमूद करते की आम्हाला के च्या श्रेणीत दिलेली अनरेडर्ड अ‍ॅरेमध्ये डुप्लिकेटची तपासणी करावी लागेल. येथे के चे मूल्य दिलेल्या अ‍ॅरेपेक्षा लहान आहे.

दिलेल्या अ‍ॅरेमध्ये एकमेकांपासून के अंतरावर डुप्लिकेट घटक आहेत का ते तपासा

उदाहरणे

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

स्पष्टीकरण

या समस्येचे निराकरण करण्यासाठी आपल्याकडे दोन पद्धती आहेत. सर्वात सोपा एक म्हणजे दोन लूप चालविणे ज्यामध्ये पहिला लूप प्रत्येक लूप दुसर्‍या लूपसाठी अंतर्गत घटक म्हणून निवडेल. यानंतर, दुसरी लूप 'के' च्या श्रेणीतील सर्व घटकांसह प्रारंभिक घटकाची तुलना करेल. परंतु हे समाधान इतके कार्यक्षम नाही की हे ओ (के * एन) ची जटिलता घेते.

परंतु आपल्याकडे आणखी एक कार्यक्षम पद्धत आहे जी समस्येचे निराकरण करू शकते O (n) वेळ गुंतागुंत म्हणतात हॅशिंग. हॅशिंग मेथडमध्ये आपण अ‍ॅरेचे सर्व एलिमेंटस ट्रॅव्हर करू आणि त्यामध्ये एलिमेंट आहे की नाही हे तपासू. जर घटक तिथे असेल तर आपण 'ट्रू' परत करू. नाहीतर आम्ही ते हॅशमध्ये जोडू आणि जर 'i' 'के' पेक्षा मोठे असेल तर अरश [ik] घटक हॅशमधून काढून टाकू.

दिलेले अ‍ॅरेमध्ये एकमेकांपासून के अंतरावर डुप्लीकेट घटक आहेत का हे तपासण्यासाठी अल्गोरिदम

  1. प्रथम रिक्त तयार करा हॅश सेट ज्यामध्ये आपण अ‍ॅरेचे घटक संचित करू.
  2. अ‍ॅरेचे सर्व घटक डावीकडून उजवीकडे वळा.
  3. घटक हॅशमध्ये आहे की नाही ते तपासा.
    • जर तेथे असेल तर परत “सत्य”.
    • अन्यथा ते घटक हॅशमध्ये जोडा.
  4. यानंतर 'I' मोठे किंवा 'के' समान असल्यास हॅशमधून अरर [ik] घटक काढा.

 

आमच्यात एक अ‍ॅरे 'अर' [] आहे ज्यामध्ये त्यातील काही घटक आहेत आणि व्हॅल्यू के ही एक रेंज आहे ज्यामध्ये डुप्लिकेट्स शोधायचे असल्यास त्यामध्ये घटक साठवण्यासाठी हॅश सेट वापरणार आहोत, आम्ही त्यातील घटक समाविष्ट करू. आमच्या हॅशमधील अ‍ॅरे एकामागून एक सेट करते जर घटक आधीपासूनच हॅश सेटमध्ये असेल तर तो खरा परत येईल आणि लूप तोडेल अन्यथा ते सेटमधील घटक सतत समाविष्ट करेल आणि सेटमधून एर [ik] एलिमेंट काढून टाकेल.

कोड

सी ++ कोड तपासण्यासाठी दिलेल्या अ‍ॅरेमध्ये एकमेकांपासून के अंतरावर डुप्लिकेट घटक आहेत का ते तपासा

#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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. हॅश सेट वापरल्याने रेषीय वेळेत समस्या सोडविणे शक्य होते. हॅश सेट वापरण्याने डेटा कार्यक्षमतेने शोधण्याची, हटविण्याची आणि समाविष्ट करण्याची क्षमता वाढवते.

स्पेस कॉम्प्लेक्सिटी

ठीक आहे) जेथे "के" विंडोमधील घटकांची संख्या आहे ज्यावर लक्ष दिले पाहिजे.