Поиск минимального расстояния между одинаковыми элементами

Question

Напишите псевдокод алгоритма, который находит в массиве два одинаковых элемента, расстояние между которыми в массиве минимально. То есть нужно найти индексы i*, j* такие, что:

i*, j* = argmin{j - i | a_i = a_j, i < j}

Покажите, какую вычислительную сложность имеет ваш алгоритм и почему. Считайте, что размер массива не более 10^7, а элементы массива - целые числа от -10^18 до 10^18.

Первое решение, что пришло в голову это перебрать каждый элемент за O(n^2) и запомнить индексы одинаковых элементов и их разницу и так искать минимальное расстояние. Второе решение, это отсортировать a_i по возрастанию и дальше сравнивать по 2 числа
Например:

list index: [00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17, 18]  
list value: [ 2,  7,  1,  2,  4,  2,  9, 10,  7,  2,  4,  4, 10,  1,  8,  2,  5,  9,  6]

Сортируем и получаем такое

list index: [02, 13, 00, 03, 05, 09, 15, 04, 10, 11, 16, 18, 01, 08, 14, 06, 17, 07, 12]  
list value: [ 1,  1,  2,  2,  2,  2,  2,  4,  4,  4,  5,  6,  7,  7,  8,  9,  9, 10, 10]

Сравниваем по 2 элемента и запоминаем разницу индексов, потом находим минимальное значение Сложность O(n log n). Как решить эту задачу за O(n)?

Answer 1

Когда есть задача добиться времени выполнения O(N), надо подумать что можно сделать за O(1) и O(logN). Пробегаемся в голове по структурам данных. Т.к. у нас есть одинаковые элементы скорее всего что-то будет связано с множествами или hashmap, нам нужно работать не только с элементами, но и индексами, поэтому скорее всего нам подойдёт именно hashmap т.к. с её помощью мы сможем хранить элементы и индексы, время выполнения операций вставка и поиск выполняется за O(1).

Можно сделать так:

Проитерироваться по всем элементам и положить их в hashmap (ключом является число, а значением будет индекс текущего элемента).
Создадим переменную, которая будет хранить минимальную разницу minDistance и зададим ей значение = размер исходного массива + 1.
При вставке в hashmap:
- Если элемента (числа) нет среди ключей hashmap, то вставляем его и текущий индекс элемента
- Если элемент присутствует в hashmap:
  - Вытаскиваем предыдущий индекс такого элемента
  - Находим разницу индексов (текущий индекс - значение по ключу в hashmap),
  - Сравниваем эту разницу с minDistance, если minDistance больше текущей разницы, то обновляем minDistance
  - Перезаписываем значение индекса для текущего элемента в hashmap текущим индексом (т.к. далее минимальная дистанция для двух одинаковых элементов будет только для тех элементов, которые были после текущего совпадения)

БЛОГ НА HUSL

Поиск минимального расстояния между одинаковыми элементами

Ответы (1 шт):