UniLecs #147. Duplicates
UniLecs
Задача: Дан массив целых чисел - arr[]. Необходимо выяснить, если такие два различных индекса i, j в массиве, что arr[i] == arr[j] и абсолютная разность между ними не более K ( |i - j| <= k).
Входные данные: arr - массив целых чисел от 1 до 10^3 элементов, элементы массива целые числа от 1 до 10^3 по модулю; K - натуральное число от 1 до 10^3
Вывод: true - если в массиве найдутся такие два индекса, удовлетворяющих условиям, в противном случае false.
Пример:
1. arr = [1, 2, 3, 1]; K = 3
Answer = true
2. arr = [1, 0, 1, 1]; K = 1
Answer = true
3. arr = [1, 2, 3, 1, 2, 3]; K = 2
Answer = false
Идея: вариантов решений этой задачи несколько, одним из самых простых и популярных подходов считается способ с помощью HashTable или Dictionary.
В словарике ключом будет являться сам элемент массива, а значением будет список индексов, где встречается этот элемент. В цикле просматриваются все элементы массива и заносятся в словарик. Также на каждой итерации для повторяющихся элементов проверяем в списке значений, есть ли такие индексы, ктр по модулю не превышают K.
Реализация: одна из реализаций с помощью Dictionary<int, List<int>> на C#
https://gist.github.com/unilecs/409bdf34787438c8ee3388e8112bd3c6