leftctrl/findtail

FindTail

Задача:

Найти повторяющееся число в исходном массиве.

Входные данные:

• Массив длины (N+1), заполненный случайными числами от 1 до N (числа могут повторяться неограниченное кол-во раз).

---

Пример: Если N = 5, то массив будет вида [5, 1, 3, 4, 5, 4].

---

Ограничения:

• Сложность алгоритма - O(n)
• Сложность по памяти - O(1)
• Исходный массив менять нельзя
• Не гарантируется присутствие в массиве всех чисел от 1 до N (числа генерятся случайным образом в рамках диапазона от 1 до N)

===

Решение:

В общем случае (для произвольных данных) нельзя обеспечить поиск повторяющихся данных в массиве с требуемыми ограничениями по сложности алгоритма.

Поэтому для решения задачи мы будем использовать особые свойства данных нашего массива:

• Числа в массиве гарантированно имеют хотя бы одно повторение - потому что их на единицу больше, чем диапазон доступных значений для заполнения массива.
• Любое число в массиве не превышает максимальный индекс этого массива: таким образом можно двигаться по массиву, начав с любой точки M{принадлежащей диапазону от 0 до N}, и далее в качестве следующего элемента брать значение M-ного элемента массива. (Обход всего массива при этом не гарантируется!)

---

Пример:

Пусть у нас есть массив [5, 1, 3, 4, 5, 4]

Начнем, например, со второго элемента.

В массиве-примере по индексу 2 лежит число 3.

По индексу 3 лежит число 4.

По индексу 4 лежит число 5.

По индексу 5 лежит число 4.

Далее алгоритм бесконечно переходит с ячейки 4 в ячейку 5 и обратно (зацикливается))

---

1. Докажем, что если двигаться по массиву описанным выше образом, мы гарантированно попадем в "петлю" (зацикливание алгоритма на одной и той же последовательности ячеек) через N+1 итераций.

Док-во: Чтобы не зациклиться, на каждой итерации мы должны получать новое (не встречавшееся ранее) значение в ячейке, а это невозможно при N возможных значений и N+1 итераций.

2. Учитывая (1) мы можем сказать, что индекс, лежащий в ячейке, в которую мы попали на N+1 итерации гарантированно участвует в "петле" (повторяющейся последовательности ячеек)

3. Выведем еще одно свойство алгоритма движения по индексам массива: двигаясь таким образом невозможно попасть в ячейку с индексом 0, т.к. по условию числа в массиве начинаются с 1.

4. Таким образом, если начать движение с 0-й ячейки, мы гарантируем что в последовательности переходов по ячейкам будет как часть вне петли (как минимум - ячейка с индексом 0), так и сама петля.

Чтобы перейти от незакольцованной части последовательности к закольцованной, в обоих из них должно встречаться одно и тоже число (оно и будет решением нашей задачи)

5. Зная индекс из (2) мы можем начать переход по ячейкам с него и посчитать, сколько итераций нужно чтобы снова вернуться к этому индексу - так мы измерим длину "петли"

6. Зная длину петли(назовем ее L), мы можем использовать два итератора, начавшие движение с нулевого индекса и отстающие друг от друга на L итераций, чтобы найти место вхождения в петлю.

Будем сравнивать на каждой итерации, куда ссылаются итераторы: когда числа по ссылкам совпадут это будет означать, что мы нашли число, которое находится в двух разных ячейках (внутри и вне петли). Это число и будет искомым дублирующимся элементом массива.