Как идентифицировать дублированное число в массиве с минимальной сложностью?

Question

Существует массив размером 10000. Он хранит числа от 1 до 10000 в случайном порядке.
Каждый номер встречается только один раз.

Теперь, если какое-либо число будет удалено из этого массива, а любое другое число будет скопировано в массив.

Как мы можем определить, какое число дублируется, с минимальной сложностью?

ПРИМЕЧАНИЕ: Мы не можем использовать другой массив.

Answer 1

Самый быстрый способ - сортировка по квадратным отверстиям на месте O (N).

Начать с первого расположения массива, a[0]. Скажем, оно имеет значение 5. Вы знаете, что 5 принадлежит a[4], поэтому поменяйте местами 0 и 4. Теперь новое значение в a[0]. Поменяйте его туда, куда нужно.

Повторяйте до a[0] == 1, затем переходите к a[1] и меняйте местами до a[1] == 2 и т. Д.

Если в какой-то момент вы попытаетесь поменять местами два одинаковых значения, значит, вы нашли дубликат!

Время выполнения: O (N) с очень низким коэффициентом и ранним выходом. Требуется хранилище: ноль.

Бонусная оптимизация: подсчитайте, сколько свопов произошло, и выйдите досрочно, если n_swaps == array_size. Это привело к улучшению на 15%, когда я реализовал аналогичный алгоритм для перестановки последовательности.

Answer 2

Вычислить сумму и сумму квадратов элементов (для суммы квадратов вам понадобятся 64-битные значения).Из них вы можете узнать, какой элемент был изменен:

Вычтите ожидаемые значения для неизмененного массива.Если x был удален, а y дублирован, вы получите разницу y - x для суммы, а y ² - x ² = (y + x) (y - x) для суммыквадраты.Из этого легко восстановить x и y.

Редактировать: Обратите внимание, что это может быть быстрее, чем сортировка по голубям, поскольку она работает линейно по массиву и, таким образом, более дружественна к кешу.

Answer 3

Почему бы просто не использовать второй массив или другую структуру данных, например, хеш-таблицу (если хотите, хеш-таблицу, в зависимости от компромисса между памятью и производительностью).Этот второй массив просто хранит количество чисел в исходном массиве.Теперь просто добавьте +/- к функции доступа исходного массива, и вы сразу получите свою информацию.

ps, когда вы написали «мы не можем использовать другой массив» - я полагаю, вы не можете изменить ОРИГИНАЛструктура данных.Однако возможно использование дополнительных структур данных ....

Answer 4

Сортировка массива, затем итерация, пока вы не нажмете два одинаковых числа в строке.