В массиве с целыми числами одно значение находится в массиве дважды. Как определить какой?
Предположим, что в массиве есть целые числа от 1 до 1 000 000.
Я знаю несколько популярных способов решения этой проблемы:
- Если включены все числа от 1 до 1 000 000, найдите сумму элементов массива и вычтите ее из общей суммы (n * n + 1/2)
- Использовать хэш-карту (требуется дополнительная память)
- Использовать битовую карту (меньше накладных расходов на память)
Недавно я наткнулся на другое решение, и мне нужна помощь в понимании логики, лежащей в его основе:
Сохраняйте единственное Радиксный аккумулятор. Вы исключаете - или аккумулятор с и индексом, и значением в этом индексе.
Тот факт, что x ^ C ^ x == C, здесь полезен, поскольку каждое число будет xor'd дважды, за исключением того, которое там дважды, которое будет отображаться как 3 раз. (x ^ x ^ x == x) И последний индекс, который появится один раз. Итак, если мы заполним аккумулятор окончательным индексом, конечным значением аккумулятора будет число, которое находится в списке дважды.
Буду признателен, если кто-нибудь поможет мне понять логику этого подхода (на небольшом примере!).