Проверете дали даден масив съдържа дублиращи се елементи на разстояние k един от друг


Ниво на трудност Лесно
Често задавани в Амазонка Avalara Цитадела FreeCharge Hacker Популярност Snapchat Snapdeal
Array Хашиш

Проблемът „Проверете дали даден масив съдържа дублиращи се елементи на разстояние 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).

Но имаме друг по-ефективен метод, който може да реши проблема в О (п) сложност на времето, наречена хеширане. В метода на хеширане ще прекосим всички елементи на масива и ще проверим дали елементът присъства в него или не. Ако елементът е там, ние ще върнем „True“. В противен случай ще го добавим към хеша и ще премахнем елемента arr [ik] от хеша, ако 'i' е по-голямо или равно на 'k'.

Алгоритъм за проверка дали даден масив съдържа дублиращи се елементи в рамките на k разстояние един от друг

  1. Първо, създайте празното хеш набор в който ще съхраняваме елементите на масива.
  2. Прекоси всички елементи на масива отляво надясно.
  3. Проверете дали елементът присъства в хеш или не.
    • Ако е там, върнете „true“.
    • В противен случай добавете този елемент към хеша.
  4. След това премахнете елемента arr [ik] от хеш, ако „I“ е по-голямо или равно на „k“.

 

Имаме масив 'arr []' с някакъв елемент в него и стойност k, която е диапазонът, в който трябва да намерим дубликати, ако има такъв, така че ще използваме хеш, за да съхраняваме елементите в него, първо ще добавим елементи на масивът в нашия хеш, зададен един по един, ако елементът вече е в хеш набора, той ще върне true и ще прекъсне цикъла, иначе непрекъснато ще вмъква елементите в набора и ще премахва елемента 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

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

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

О (п) където "н" е броят на елементите в масива. Използването на хеш набор позволява решаване на проблема за линейно време. Тъй като използването на хеш набор подобрява възможността за ефективно търсене, изтриване и вмъкване на данни.

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

Добре) където „К“ е броят на елементите в прозореца, които трябва да бъдат разгледани.