ఇచ్చిన శ్రేణి ఒకదానికొకటి k దూరం లోపల నకిలీ మూలకాలను కలిగి ఉందో లేదో తనిఖీ చేయండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ అవలారా సిటాడెల్ ఫ్రీచార్జ్ 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

వివరణ

ఈ సమస్యను పరిష్కరించడానికి మాకు రెండు పద్ధతులు ఉన్నాయి. సరళమైనది రెండు లూప్‌లను అమలు చేయడం, దీనిలో మొదటి లూప్ ప్రతి మూలకాన్ని రెండవ లూప్ 'ఇన్నర్ లూప్' కోసం ప్రారంభ మూలకంగా ఎంచుకుంటుంది. ఆ తరువాత, రెండవ లూప్ ప్రారంభ మూలకాన్ని 'k' పరిధిలోని అన్ని మూలకాలతో పోలుస్తుంది. కానీ ఈ పరిష్కారం సమర్థవంతంగా లేదు, ఇది O (k * n) యొక్క సంక్లిష్టతను తీసుకుంటుంది.

కానీ మనకు మరో సమర్థవంతమైన పద్ధతి ఉంది, ఇది సమస్యను పరిష్కరించగలదు పై) సమయం సంక్లిష్టత అంటారు హాషింగ్. హాషింగ్ పద్ధతిలో, మేము శ్రేణి యొక్క అన్ని అంశాలను దాటుతాము మరియు మూలకం దానిలో ఉందో లేదో తనిఖీ చేస్తాము. మూలకం అక్కడ ఉంటే, అప్పుడు మేము 'ట్రూ' అని తిరిగి వస్తాము. లేకపోతే మనం దానిని హాష్‌కు జోడించి, 'i' 'k' కన్నా ఎక్కువ లేదా సమానంగా ఉంటే హాష్ నుండి అర్ర్ [ik] మూలకాన్ని తొలగిస్తాము.

ఇచ్చిన శ్రేణి ఒకదానికొకటి k దూరం లోపల నకిలీ అంశాలను కలిగి ఉందో లేదో తనిఖీ చేసే అల్గోరిథం

  1. మొదట, ఖాళీని సృష్టించండి హాష్ సెట్ దీనిలో మేము శ్రేణి యొక్క అంశాలను నిల్వ చేస్తాము.
  2. శ్రేణి యొక్క అన్ని అంశాలను ఎడమ నుండి కుడికి ప్రయాణించండి.
  3. మూలకం హాష్‌లో ఉందో లేదో తనిఖీ చేయండి.
    • అది అక్కడ ఉంటే “నిజం” అని తిరిగి ఇవ్వండి.
    • లేకపోతే ఆ మూలకాన్ని హాష్‌కు జోడించండి.
  4. ఆ తరువాత 'I' ఎక్కువ లేదా 'k' కు సమానంగా ఉంటే హాష్ నుండి arr [ik] మూలకాన్ని తొలగించండి.

 

మనకు 'అర్ర్ []' అనే శ్రేణి ఉంది, దానిలో కొన్ని మూలకాలు ఉన్నాయి మరియు విలువ k, ఇది ఏదైనా ఉంటే మనం నకిలీలను కనుగొనవలసి ఉంటుంది, అందువల్ల దానిలోని మూలకాలను నిల్వ చేయడానికి హాష్ సెట్‌ను ఉపయోగిస్తాము, మొదట మనం మూలకాలను జోడిస్తాము మూలకం ఇప్పటికే హాష్ సెట్‌లో ఉంటే మా హాష్‌లోని శ్రేణి ఒక్కొక్కటిగా సెట్ అవుతుంది, అప్పుడు అది నిజం అవుతుంది మరియు లూప్‌ను విచ్ఛిన్నం చేస్తుంది, అది నిరంతరం సెట్‌లోని మూలకాలను చొప్పించి, సెట్ నుండి అర్ర్ [ik] మూలకాన్ని తొలగిస్తుంది.

కోడ్

ఇచ్చిన శ్రేణి ఒకదానికొకటి k దూరం లోపల నకిలీ మూలకాలను కలిగి ఉందో లేదో తనిఖీ చేయడానికి 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

ఇచ్చిన శ్రేణి ఒకదానికొకటి k దూరం లోపల నకిలీ మూలకాలను కలిగి ఉందో లేదో తనిఖీ చేయడానికి జావా కోడ్

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” శ్రేణిలోని మూలకాల సంఖ్య. హాష్ సెట్‌ను ఉపయోగించడం వల్ల సరళ సమయంలో సమస్యను పరిష్కరించడానికి అనుమతిస్తుంది. హాష్ సెట్‌ను ఉపయోగించడం వలన డేటాను సమర్ధవంతంగా శోధించడం, తొలగించడం మరియు చొప్పించే సామర్థ్యాన్ని పెంచుతుంది.

అంతరిక్ష సంక్లిష్టత

అలాగే) (ఇక్కడ “క” విండోలోని మూలకాల సంఖ్య చూడవలసిన అవసరం ఉంది.