Найдите два числа, которые появляются только один раз - разделяй и властвуй

Question

Учитывая массив, в котором каждый элемент встречается дважды, мне нужно найти, какие два числа в массиве появляются только один раз. Максимальный объем дополнительной памяти составляет O (1).

Я нашел это удивительное решение: https://medium.com/@gurupad93 / two-numbers-that-appearance-once-b89e92a9334b

The проблема в том, что мое решение должно быть разделяй и властвуй , и я понимаю, что решение, которое я нашел, - нет.

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

Есть предложения?

Большое вам спасибо!

Answer 1

Я предполагаю, что это целые положительные числа. В списке четное количество элементов. Вы вычисляете среднее значение и делите список на два подсписка, ниже и выше среднего. Тогда либо оба имеют нечетное количество элементов, либо оба четное. В нечетном случае вы знаете, что каждый подсписок содержит один синглтон, и вы решаете проблему с одним синглом для каждого из них. В четном случае вы знаете, что один из подсписок не имеет сингла, т.е. является парным, а другой - двумя. Вы решаете, какое из них является парным, и продолжаете работать над другим, рекурсивно решая проблему двух синглтонов.

Если целые числа представлены в стандартном двоичном формате, вы можете выполнить XOR для всех из них, чтобы решить, спарены ли они. В противном случае, если они представлены в двоично-десятичном формате, с плавающей запятой или чем-либо еще, где представитель не уникален, вы можете использовать следующий тест: список целых чисел является парным тогда и только тогда, когда произведение всех элементов является квадратом. Вычислите exp (1/2 суммы (log xi)), и если оно целое, список будет парным, иначе - нет.

Но решение в ссылке, по общему признанию, намного лучше, чем это.

Answer 2

Задачу можно разделить на древовидную структуру (аналогичную древовидной структуре сортировки слиянием), и каждая секция возвращает значение xor своих элементов родителю. Таким образом, мы получаем значение xor двух чисел, которые появляются в массиве только один раз.

Из проблемы ясно, что значение xor имеет как минимум один ненулевой бит.

Предположим, что значение xor равно X , а его i -й бит не равен нулю.

Теперь мы снова разделим задачу на древовидную структуру. и рассмотрим элементы, у которых установлен i -й бит, для вычисления xor. Это значение возвращается родителю. Узел root получит xor-значение элементов, для которых установлен i -й бит. Назовем это значение Y.

Следовательно, два числа - Y и X xor Y .

Answer 3

Мне удалось найти алгоритм ответа на свой вопрос:

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

У меня есть алгоритм, который может возвращаться, когда элемент, появляющийся однажды, является только одним (с использованием XOR для всех элементов). Если ни один элемент не появляется только один раз, результат XOR равен 0.

Я запускаю этот алгоритм на обоих из двух подмассивов, два варианта:

• Если алгоритм выводит 0 в одном массиве, тогда этот элемент наверняка не находится в этом подмассиве, и мы вызываем функцию рекурсивно на другой половине.

• Если (и только если) алгоритм выводит два числа отличные от 0, это означает, что результаты разделились по массивам. В этом случае эти два числа также будут результатом проблемы.

Обратите внимание, что нет других вариантов, кроме этих двух.

Пространственная сложность составляет O (1)

Временная сложность: у нас есть некоторые операции, которые стоят O (n), мы делим на каждой итерации половину массива, получаем:

T (n) = T (n / 2) + O (n) -> (Основная теорема) -> O (n)

Answer 4

Выберите первый бит.

Разделите числа с этим набором битов и числа с этим нулевым битом.

Вы можете использовать такую ​​процедуру, как разделение, в быстрой сортировке - найдите крайнее левое число с одним битом, найдите крайнее правое число с нулевым битом, поменяйте их местами, продолжайте, пока левый и правый индексы не встретятся. левая и правая части с учетом следующего бита.

Сделайте это рекурсивно со следующими битами, пока размер части не станет 1 или 2.

В первом случае вы нашли одно из необходимых чисел .

Во втором случае проверьте, различны ли числа.

---

Надеюсь, эти подсказки помогут реализовать возможный подход «разделяй и властвуй».