Нахождение повторяющегося элемента

Question

В массиве с целыми числами от 1 до 1 000 000 или, скажем, очень большим значением, если одно значение встречается дважды дважды.Как вы определяете, какой из них?

Я думаю, что мы можем использовать растровое изображение, чтобы пометить элементы, а затем снова пересечь все, чтобы найти повторный элемент.Но я думаю, что это процесс с высокой сложностью. Есть ли лучший способ?

Answer 1

Это звучит как домашняя работа или вопрос на собеседовании ... так что вместо того, чтобы давать ответ, вот подсказка.

Какие вычисления вы можете сделать для целого ряда, ответ на который вы можете определитьдосрочно?

Как только вы поймете ответ на этот вопрос, вы сможете понять это ... если вы все еще не можете понять это ... (и это не домашняя работа) Я будуопубликовать решение:)

РЕДАКТИРОВАТЬ: ОК.Итак, вот элегантное решение ... если список содержит ВСЕ целые числа в пределах диапазона.

Мы знаем, что все значения от 1 до N должны присутствовать в списке.Используя Guass 'формулу , мы можем быстро вычислить ожидаемое значение диапазона целых чисел:

Sum(1..N) = 1/2 * (1 + N) * Count(1..N).

Поскольку мы знаем ожидаемую сумму, все, что нам нужно сделать, - это перебрать все значенияи суммировать их значения.Различие между этой суммой и ожидаемой суммой является дублирующим значением.

РЕДАКТИРОВАТЬ: Как прокомментировали другие, вопрос не утверждает, что диапазон содержит все целые числа ... в этом случае вы должны решить, хотите ли вы оптимизировать память или время.

Если вы хотите выполнить операцию с использованием O (1) хранилища ,Вы можете выполнить сортировку списка по месту.При сортировке вы должны проверять соседние элементы.Как только вы увидите дубликат, вы знаете, что можете остановиться.Оптимальная сортировка - это операция O (n log n) в среднем, которая устанавливает верхнюю границу для поиска дубликата таким образом.

Если вы хотите оптимизировать по скорости, вы можете использовать дополнительный O(n) хранилище .Используя HashSet (или аналогичную структуру), вставляйте значения из своего списка, пока не решите, что вставляете дубликат в HashSet.Вставка n элементов в HashSet - это в среднем операция O (n), которая устанавливает это как верхнюю границу для этого метода.

Answer 2

Предполагая, что массив имеет длину n

Предположим, я облегчил проблему и пообещал вам, что повторяющиеся элементы были в массиве так, что первый был в первых n / 2 элементах, а второй был в последних n / 2 элементах. Теперь мы можем подумать о том, чтобы поиграть в игру, в которой каждый из двух человек содержит цепочку из n / 2 элементов и хочет знать, сколько сообщений они должны отправить, чтобы убедиться, что ни один из их элементов не совпадает. Поскольку первый игрок может имитировать запуск любого алгоритма, который проходит через массив и отправляет содержимое своей памяти второму игроку, нижняя граница количества сообщений, которые им необходимо отправить, подразумевает нижнюю границу памяти требования любого алгоритма.

Но в этой простой игре легко увидеть, что им нужно отправлять n / 2 сообщений, чтобы убедиться, что они не содержат ни одного из тех же элементов, что дает нижнюю границу.

Редактировать: Это обобщает, чтобы показать, что для алгоритмов, которые делают k, проходит через массив и используют память m, что m * k = Omega (n). И легко увидеть, что таким образом вы можете обменять память на время таким образом.

Конечно, если вы хотите использовать алгоритмы, которые не просто принимают проходы через массив, вы можете сделать лучше, как уже предлагалось: отсортировать массив, а затем выполнить 1 проход. Это занимает время O (nlogn) и пространство O (1). Но с любопытством обратите внимание, что это доказывает, что любой алгоритм сортировки, который только что проходит через массив, должен занимать время Omega (n ^ 2)! Алгоритмы сортировки, которые нарушают границу n ^ 2, должны иметь произвольный доступ.

Answer 3

Временная сложность растрового решения составляет O (n), и не похоже, что вы могли бы добиться большего успеха, чем это.Однако это займет много памяти для общего списка чисел.Сортировка чисел является очевидным способом обнаружения дубликатов и не требует дополнительного места, если вы не против изменения текущего порядка.

Answer 4

вы можете попытаться использовать биты в качестве хэш-карты:

1 в позиции k означает, что число k произошло до

0 в позиции k означает, что число k не произошло до

псевдокод:

0. assume that your array is A
1. initialize bitarray(there is nice class in c# for this) of 1000000 length filled with zeros
2. for each num in A:
   if bitarray[num] 
      return num
   else
      bitarray[num] = 1
   end