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

Question

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

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

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

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

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

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

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

Answer 1

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

int accumulator = 0;

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

accumulator ^= (i ^ v)

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

accumulator ^= (i ^ i)

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

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

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

int accumulator = N;

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

Answer 2

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

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

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

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

Answer 3

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

Непростое решение - пройти весь массив и отсортировать его, как вы делаете. При сортировке убедитесь, что нет повторяющихся значений, т.е. реализуйте абстрактный тип данных «set». Это, вероятно, потребует выделения второго массива, а сортировка займет много времени. Я не знаю, требует ли он больше или меньше времени, чем хитрые уловки XOR.

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

Answer 4

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

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

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