Проблема

  • Найдите дубликат в массиве
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) и не требует изменения входного списка.

дальнейшее чтение