Проверьте, содержит ли данный массив повторяющиеся элементы на расстоянии k друг от друга


Сложный уровень Легко
Часто спрашивают в Амазонка Avalara Цитадель Свободный заряд Хакер Rank Snapchat Snapdeal
массив Hash

Задача «Проверить, содержит ли данный массив повторяющиеся элементы на расстоянии 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. Проверьте, присутствует ли элемент в хэше или нет.
    • Если он там, верните «истина».
    • Иначе добавьте этот элемент в хеш.
  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

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

Сложность времени

О (п) в котором «Н» - количество элементов в массиве. Использование набора хешей позволяет решить задачу за линейное время. Поскольку использование хеш-набора расширяет возможности эффективного поиска, удаления и вставки данных.

Космическая сложность

Хорошо) в котором "К" это количество элементов в окне, которые необходимо просмотреть.