найти дубликаты

Question

Вам дан массив элементов.Некоторые / все они являются дубликатами.Найти их в 0 (n) времени и 0 (1) пространстве.Свойство входов - Число в диапазоне 1..n, где n - предел массива.

Answer 1

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

Answer 2

Поскольку количество элементов в массиве и , диапазон массива является переменным в зависимости от n, я не верю, что вы можете сделать это.Я могу ошибаться, лично я сомневаюсь в этом, но раньше я ошибался: -)

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

Если диапазон был фиксированный (скажем, 1..m),Вы можете сделать это следующим образом:

dim quant[1..m]
for i in 1..m:
    quant[m] = 0
for i in 1..size(array):
    quant[array[i]] = quant[array[i]] + 1
for i in 1..m:
    if quant[i] > 1:
        print "Duplicate value: " + i

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