Рубрики

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

Дан несортированный массив, который может содержать дубликаты. Также дано число k, которое меньше размера массива. Напишите функцию, которая возвращает true, если массив содержит дубликаты на расстоянии k.

Примеры:

Input: k = 3, arr[] = {1, 2, 3, 4, 1, 2, 3, 4}
Output: false
All duplicates are more than k distance away.

Input: k = 3, arr[] = {1, 2, 3, 1, 4, 5}
Output: true
1 is repeated at distance 3.

Input: k = 3, arr[] = {1, 2, 3, 4, 5}
Output: false

Input: k = 3, arr[] = {1, 2, 3, 4, 4}
Output: true

Простое решение — запустить два цикла. Внешний цикл выбирает каждый элемент 'arr [i]' как начальный элемент, внутренний цикл сравнивает все элементы, которые находятся на расстоянии k от 'arr [i]'. Временная сложность этого решения составляет O (kn).

Мы можем решить эту проблему за Θ (n) времени, используя хеширование. Идея состоит в том, чтобы добавить элементы в хэш. Мы также удаляем элементы, которые находятся на расстоянии более k от текущего элемента. Ниже приводится подробный алгоритм.

1) Создать пустую хеш-таблицу.
2) Пройдите все элементы слева направо. Пусть текущий элемент будет 'arr [i]'
… .A) Если текущий элемент 'arr [i]' присутствует в хеш-таблице, вернуть true.
… .B) В противном случае добавьте arr [i] в хеш и удалите arr [ik] из хеша, если i больше или равно k

C ++

#include<bits/stdc++.h>

using namespace std;

  
/ * C ++ программа для проверки, если данный массив содержит дубликат

   элементы на расстоянии k друг от друга * /

bool checkDuplicatesWithinK(int arr[], int n, int k)

{

    // Создает пустой хэшсет

    unordered_set<int> myset;

  

    // Обход входного массива

    for (int i = 0; i < n; i++)

    {

        // Если хэш уже присутствует, то мы нашли

        // дубликат в пределах k расстояния

        if (myset.find(arr[i]) != myset.end())

            return true;

  

        // Добавить этот элемент в hashset

        myset.insert(arr[i]);

  

        // Удалить элемент k + 1

        if (i >= k)

            myset.erase(arr[i-k]);

    }

    return false;

}

  
// Метод драйвера для проверки вышеуказанного метода

int main ()

{

    int arr[] = {10, 5, 3, 4, 3, 5, 6};

    int n = sizeof(arr) / sizeof(arr[0]);

    if (checkDuplicatesWithinK(arr, n, 3))

        cout << "Yes";

    else

        cout << "No";

}

  
// Эта статья предоставлена Чхави

Джава

/ * Java-программа для проверки, если данный массив содержит дубликат

   элементы на расстоянии k друг от друга * /

import java.util.*;

  

class Main

{

    static boolean checkDuplicatesWithinK(int arr[], int k)

    {

        // Создает пустой хэшсет

        HashSet<Integer> set = new HashSet<>();

  

        // Обход входного массива

        for (int i=0; i<arr.length; i++)

        {

            // Если хэш уже присутствует, то мы нашли

            // дубликат в пределах k расстояния

            if (set.contains(arr[i]))

               return true;

  

            // Добавить этот элемент в hashset

            set.add(arr[i]);

  

            // Удалить элемент k + 1

            if (i >= k)

              set.remove(arr[i-k]);

        }

        return false;

    }

  

    // Метод драйвера для проверки вышеуказанного метода

    public static void main (String[] args)

    {

        int arr[] = {10, 5, 3, 4, 3, 5, 6};

        if (checkDuplicatesWithinK(arr, 3))

           System.out.println("Yes");

        else

           System.out.println("No");

    }

}

Python 3

# Python 3 программа для проверки наличия заданного массива
# содержит повторяющиеся элементы на расстоянии k
# друг от друга

def checkDuplicatesWithinK(arr, n, k):

  

    # Создает пустой список

    myset = []

  

    # Обход входного массива

    for i in range(n):

      

        # Если уже присутствует хеш, то мы

        # нашел дубликат в пределах k расстояния

        if arr[i] in myset:

            return True

  

        # Добавить этот элемент в hashset

        myset.append(arr[i])

  

        # Удалить элемент k + 1

        if (i >= k):

            myset.remove(arr[i - k])

    return False

  
Код водителя

if __name__ == "__main__":

      

    arr = [10, 5, 3, 4, 3, 5, 6]

    n = len(arr)

    if (checkDuplicatesWithinK(arr, n, 3)):

        print("Yes")

    else:

        print("No")

  
# Этот код предоставлен ita_c

C #

/ * C # программа для проверки, если данный
массив содержит повторяющиеся элементы
на расстоянии k друг от друга *

using System;

using System.Collections.Generic;

  

class GFG

{

    static bool checkDuplicatesWithinK(int []arr, int k)

    {

        // Создает пустой хэшсет

        HashSet<int> set = new HashSet<int>();

  

        // Обход входного массива

        for (int i = 0; i < arr.Length; i++)

        {

            // Если хэш уже присутствует, то мы нашли

            // дубликат в пределах k расстояния

            if (set.Contains(arr[i]))

                return true;

  

            // Добавить этот элемент в hashset

            set.Add(arr[i]);

  

            // Удалить элемент k + 1

            if (i >= k)

                set.Remove(arr[i - k]);

        }

        return false;

    }

  

    // Код драйвера

    public static void Main (String[] args)

    {

        int []arr = {10, 5, 3, 4, 3, 5, 6};

        if (checkDuplicatesWithinK(arr, 3))

            Console.WriteLine("Yes");

        else

            Console.WriteLine("No");

    }

}

  
// Этот код был добавлен
// от 29AjayKumar

Выход:

Yes

Эта статья предоставлена Anuj . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

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

0.00 (0%) 0 votes