Проблема
- Найдите дубликат в массиве
Given an array of n + 1 integers between 1 and n, find one of the duplicates.
If there are multiple possible answers, return one of the duplicates.
If there is no duplicate, return -1.
Example:
Input: [1, 2, 2, 3]
Output: 2
Input: [3, 4, 1, 4, 1]
Output: 4 or 1
Категория: Массивы
Процесс решения
Прежде чем увидеть решения, давайте немного поговорим о проблеме. Мы получаем массив из n + 1
элементов с целыми числами от 1 до n
.
Например, с массивом из 5 целых чисел это означает, что каждое целое число будет иметь значение от 1 до 4 (включительно). Это означает, что автоматически будет хотя бы один дубликат.
Единственное исключение - массив размером 1. Это единственный случай, когда мы должны вернуть -1.
Грубая сила
Решением перебора является реализация двух вложенных циклов следующим образом:
for i = 0; i < size(a); i++ { for j = i+1; j < size(a); j++ { if(a[i] == a[j]) return a[i] } }
O (n²) временная сложность и O (1) пространственная сложность.
Подсчет итераций
Другое решение - иметь структуру данных для подсчета количества итераций каждого целого числа. Это решение может быть реализовано как с массивом, так и с хеш-таблицей.
Реализация на Java:
Значение индекса i
представляет количество итераций i+1
.
Это решение занимает O (n) время, но O (n) пространство, поскольку нам нужна дополнительная структура.
Сортированный массив
Если мы применим технику упрощения, мы могли бы попытаться найти решение с отсортированным массивом.
В этом случае нам просто нужно будет сравнить каждый элемент с его правым соседом.
В Java:
O (1) в пространстве, но O (n log (n)) по времени, так как нам нужно предварительно отсортировать коллекцию.
Сумма элементов
Мы можем подумать о том, чтобы суммировать элементы массива и сравнивать его с 1 + 2 +… + n.
Давайте посмотрим на пример:
Input: [1, 4, 3, 3, 2, 5] Sum = 18 As in this example, we have n = 5: Sum of 1 to 5 = 1 + 2 + 3 + 4 + 5 = 15 => 18 - 15 = 3 so 3 is the duplicate
В этом примере мы можем найти решение за время O (n) и пространство O (1). Тем не менее, он работает только в том случае, если у нас есть один дубликат.
Контрпример:
Input: [1, 2, 3, 2, 3, 4] Sum = 15 As in this example we have n = 5, Sum of 1 to 5 = 1 + 2 + 3 + 4 + 5 = 15 /!\ Not working
Это направление никуда не денется. Но иногда нам нужно кое-что попробовать, чтобы найти наиболее оптимальное решение.
Маркер
Здесь есть кое-что интересное. Пока что наши решения не используют тот факт, что каждое целое число находится в диапазоне от 1 до n
. Из-за этого интересного ограничения каждое значение имеет собственный соответствующий индекс в массиве.
Решение состоит в том, чтобы рассматривать этот конкретный массив как своего рода связанный список. Любой индекс указывает на значение этого индекса.
Мы перебираем каждый элемент и помечаем его соответствующий индекс, устанавливая его знак на минус. Если мы уже отметили его как отрицательный, значит, его индекс дублирован.
Давайте посмотрим на конкретный пошаговый пример:
Input: [2, 3, 3, 1] * Index 0: Absolute value = 2 Put a minus sign to a[2] => [2, 3, -3, 1] * Index 1: Absolute value = 3 Put a minus sign to a[3] => [2, 3, -3, -1] * Index 2: Absolute value = 3 As a[3] is already negative, it means 3 is a duplicate
В Java:
Это решение - время O (n) и пространство O (1). Тем не менее, требуется изменить входной список.
Техника бегуна
Существует другое решение, которое также рассматривает данный массив как своего рода связанный список (опять же, это возможно из-за ограничения, что каждое целое число находится в диапазоне от 1 до n
).
Разберем пример [1, 2, 3, 4, 2]
:
Используя это представление, мы можем просто сказать, что существует дубликат, когда цикл действительно существует. Причем дубликат - это точка входа в цикл (в данном случае второй элемент).
Если мы черпаем вдохновение из алгоритма поиска циклов Флойда, мы можем вывести следующий алгоритм:
- Инициируйте два указателя
slow
иfast
- Для каждого шага медленный перемещается на один шаг за раз с
slow = a[slow]
, тогда как быстрый - на два шага за раз сfast = a[a[fast]]
- Когда
slow == fast
, мы находимся в цикле
Алгоритм завершен? Еще нет. Точкой входа в этот цикл будет дубликат. Мы должны сбросить slow
и шаг за шагом перемещать оба указателя, пока они снова не станут равными.
Возможная реализация на Java:
Это решение занимает время O (n) и пространство O (1) и не требует изменения входного списка.