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

Предположим, что массив имеет целые числа от 1 до 1000000.

Я знаю несколько популярных способов решения этой проблемы:

Если все числа от 1 до 1 000 000 включены, найдите сумму элементов массива и вычтите ее из общей суммы (n * n + 1/2)
Использование хэш-карты (требуется дополнительная память)
Используйте бит-карту (меньше служебных данных памяти)

Недавно я встретил другое решение, и мне нужна помощь в понимании логики, стоящей за ней:

Держите один накопитель радикса. Вы эксклюзивный или аккумулятор с как индекс, так и значение в этом индексе.

Здесь полезен тот факт, что x ^ C ^ x == C, так как каждое число будет xor'd дважды, кроме того, что там дважды, что появится 3 раз. (x ^ x ^ x == x) И последний индекс, который появится один раз. Поэтому, если мы выберем аккумулятор с окончательным индексом, конечное значение будет числом, которое находится в списке дважды.

Буду признателен, если кто-то может помочь мне понять логику этого подхода (с небольшим примером!).

Ответ 1

Предположим, что у вас есть аккумулятор

int accumulator = 0;

На каждом шаге вашего цикла вы XOR накопитель с i и v, где i - индекс итерации цикла, а v - значение в i -й позиции массив.

accumulator ^= (i ^ v)

Обычно i и v будут одного и того же номера, поэтому вы в конечном итоге выполните

accumulator ^= (i ^ i)

Но i ^ i == 0, поэтому в итоге это будет no-op, а значение аккумулятора останется нетронутым. В этот момент я должен сказать, что порядок чисел в массиве не имеет значения, потому что XOR является коммутативным, поэтому даже если массив перетасовывается, чтобы начать с результата в конце, все равно должно быть 0 (начальное значение аккумулятор).

Теперь, что, если число встречается дважды в массиве? Очевидно, что это число будет появляться три раза в XORing (один для индекса, равный числу, один для нормального появления числа и один для дополнительного внешнего вида). Кроме того, одно из других чисел будет отображаться только один раз (только для его индекса).

В этом решении теперь предполагается, что число, которое появляется только один раз, равно последнему индексу массива, или, другими словами: диапазон чисел в массиве смежный и начиная с первого индекса, который будет обработан (edit: спасибо кафе за этот хед-ап комментарий, это то, что я имел в виду на самом деле, но я полностью испортил его при написании). При этом (N появляется только один раз) в качестве заданного, считайте, что начиная с

int accumulator = N;

эффективно заставляет N снова дважды появляться в XORing. На этом этапе мы остаемся с цифрами, которые появляются ровно в два раза, и только одно число, которое появляется три раза. Поскольку дважды отображаемые числа будут XOR out до 0, окончательное значение аккумулятора будет равно числу, которое появляется три раза (т.е. Один дополнительный).

Ответ 2

Каждое число от 1 до 10,001 включительно отображается как индекс массива. (Не являются ли массивы C 0-индексированными? Ну, это не имеет значения, если мы согласны с тем, что значения массива и индексы начинаются с нуля или оба начинаются с 1. Я пойду с массивом, начиная с 1, так как этот вопрос, кажется, говорит.)

В любом случае, да, каждое число от 1 до 10,001 включительно появляется ровно один раз в качестве индекса массива. Каждое число от 1 до 10 000 включительно также отображается как значение массива точно один раз, за исключением дублированного значения, которое происходит дважды. Итак, математически, вычисление, которое мы делаем в целом, следующее:

1 xor 1 xor 2 xor 2 xor 3 xor 3 xor ... xor 10,000 xor 10,000 xor 10,001 xor D

где D - дублируемое значение. Разумеется, термины в вычислении, вероятно, не появляются в этом порядке, но xor является коммутативным, поэтому мы можем изменить порядок, как нам нравится. А n xor n равно 0 для каждого n. Таким образом, приведенное выше упрощает

10,001 xor D

xor это с 10,001, и вы получите D, дублируемое значение.

Ответ 3

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

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

Конечно, если массив отсортирован для начала, все намного проще. Поэтому во многом зависит от того, как значения распределяются по всему массиву.

Ответ 4

Вопрос: интересуетесь ли вы умением делать умные, но сугубо академические хорные трюки, мало относящиеся к реальному миру, или вы хотите это знать, потому что в реальном мире вы можете писать программы, которые используют массивы? Этот ответ касается последнего случая.

Беспросветное решение состоит в том, чтобы пройти через весь массив и отсортировать его так же, как и вы. Пока вы сортируете, убедитесь, что нет повторяющихся значений, т.е. реализуйте абстрактный тип данных "set". Это, вероятно, потребует выделения второго массива, и сортировка потребует много времени. Является ли это более или менее трудоемким, чем умные xor трюки, я не знаю.

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