Проверите да ли дати низ садржи дуплиране елементе на удаљености од к један од другог


Ниво тешкоће Лако
Често питани у амазонка Авалара Цитадела Бесплатно ХацкерРанк Снапцхат Снапдеал
Ред Хасх

Проблем „Провери да ли дати низ садржи дуплиране елементе на међусобној удаљености од к“ наводи да морамо да проверимо дупликате у датом неуређеном низу у опсегу к. Овде је вредност к мања од датог низа.

Проверите да ли дати низ садржи дуплиране елементе на удаљености од к један од другог

Примери

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

Објашњење

Имамо две методе за решавање овог проблема. Једноставније је покренути две петље у којима ће прва петља одабрати сваки елемент као почетни елемент за другу петљу „Унутрашња петља“. Након тога, друга петља ће упоредити почетни елемент са свим елементима у опсегу 'к'. Али ово решење није толико ефикасно, потребна је временска сложеност О (к * н).

Али имамо још један ефикаснији метод који може решити проблем у Он) временска сложеност названа хасхинг. У методи хеширања прећи ћемо све елементе низа и проверићемо да ли је елемент присутан у њему или не. Ако је елемент унутра, вратићемо „Труе“. Иначе ћемо га додати у хеш и уклонити елемент арр [ик] из хеша ако је „и“ веће или једнако „к“.

Алгоритам за проверу садржи ли дати низ дуплиране елементе на међусобној удаљености од к

  1. Прво створите празно хасх сет у коју ћемо сместити елементе низа.
  2. Пређите све елементе низа с лева на десно.
  3. Проверите да ли је елемент присутан у хешу или не.
    • Ако је тамо, вратите „истина“.
    • Иначе додајте тај елемент у хеш.
  4. Након тога уклоните елемент арр [ик] из хеша ако је „И“ веће или једнако „к“.

 

Имамо низ 'арр []' са неким елементом у себи и вредност к која је опсег у којем морамо пронаћи дупликате ако постоји, па ћемо користити хеш сет за чување елемената у њему прво ћемо додати елементе низ у нашем хеш-скупу поставља се један по један, ако је елемент већ у хеш-скупу, он ће вратити вредност труе и прекинути петљу, иначе ће непрекидно уметати елементе у скуп и уклањати елемент арр [ик] из скупа.

код

Ц ++ код за проверу садржи ли дати низ дуплиране елементе на удаљености од к један од другог

#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

Анализа сложености

Сложеност времена

Он) где „Н“ је број елемената у низу. Коришћење Хасх скупа омогућава решавање проблема у линеарном времену. Будући да коришћење хеш-скупа побољшава могућност ефикасног претраживања, брисања и уметања података.

Сложеност простора

У реду) где „К“ је број елемената у прозору који треба погледати.