Ստուգեք, արդյոք տվյալ զանգվածը կրկնօրինակ տարրեր է պարունակում միմյանցից k հեռավորության վրա


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Ավալարա Միջնաբերդ Անվճար լիցքավորում HackerRank Snapchat Snapdeal
Դասավորություն Խանգարել

«Ստուգեք, արդյոք տվյալ զանգվածը պարունակում է կրկնօրինակ տարրեր միմյանցից k հեռավորության վրա» խնդիրը ասում է, որ մենք պետք է ստուգենք 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) բարդություն:

Բայց մենք ունենք մեկ այլ ավելի արդյունավետ մեթոդ, որը կարող է լուծել խնդիրը O (n) ժամանակի բարդությունը կոչվում է ծիծաղել, Հաշման եղանակով մենք կանցնենք զանգվածի բոլոր տարրերի միջև և կփորձենք, որ տարրը առկա է դրանում, թե ոչ: Եթե ​​տարրն այնտեղ է, ապա մենք կվերադարձնենք «ueիշտ»: Այլապես մենք այն կավելացնենք հաշին և կհանենք arr [ik] տարրը հաշից, եթե «i» - ը մեծ է կամ հավասար է «k» - ի:

Ալգորիթմ ՝ Ստուգելու համար, արդյոք տվյալ զանգվածը կրկնօրինակ տարրեր է պարունակում միմյանցից k հեռավորության վրա

  1. Նախ, ստեղծեք դատարկը հաշ հավաքածու որում մենք պահելու ենք զանգվածի տարրերը:
  2. Ձախից աջ անցեք զանգվածի բոլոր տարրերը:
  3. Ստուգեք ՝ տարրը առկա է hash- ում, թե ոչ:
    • Եթե ​​այնտեղ է, ապա վերադարձիր «ճշմարիտ»:
    • Ուրիշ էլ այդ տարրը ավելացնեք հեշում:
  4. Դրանից հետո հեշից հանեք arr [ik] տարրը, եթե «I» - ն ավելի մեծ է կամ հավասար է «k» - ի:

 

Մենք ունենք «arr []» զանգված, որի մեջ կա որոշ տարր և k արժեք, որն այն տիրույթն է, որում մենք պետք է կրկնօրինակներ գտնենք, եթե կա այդպիսին, օգտագործելու է hash set ՝ տարրերը դրանում պահելու համար, նախ կավելացնենք մեր hash հավաքածուի զանգվածը մեկ առ մեկ, եթե տարրը արդեն hash հավաքածուում է, ապա այն կվերադառնա ճշմարիտ և կկոտրի օղակը, այլապես այն անընդմեջ կտեղադրի տարրերը հավաքածուի մեջ և arr [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

Java կոդ ՝ ստուգելու համար, արդյոք տվյալ զանգվածը կրկնօրինակ տարրեր է պարունակում միմյանցից 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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Hash Set- ի օգտագործումը թույլ է տալիս խնդիրը լուծել գծային ժամանակում: Քանի որ հաշ հավաքածուն օգտագործելը մեծացնում է տվյալների արդյունավետ որոնման, ջնջման և տեղադրման հնարավորությունը:

Տիեզերական բարդություն

Լավ) որտեղ «Կ» պատուհանում տարրերի քանակն է, որը պետք է դիտարկել: