Топ контрибуторов
loading
loading
Знаете ли Вы, что

Список полученных сертификатов находится на странице Вашего профиля. Сертификаты можно распечатать или разместить на Вашем сайте.

Лента обновлений
ссылка Feb 22 17:21
Комментарий от raja_kajiev:
Плохой вопрос! Т.к. если думать, что второй .where()...
ссылка Feb 22 12:22
Комментарий от jackd2pkt:
Задания в основном достаточно странные, много таких, к...
ссылка Feb 21 09:17
Комментарий от subbotenko:
Вообще и без SRC и без RES проект прекрасно скомпилир...
ссылка Feb 21 08:29
Комментарий от Partyhard:
row это строка, а значит объединени будет происходить ...
ссылка Feb 20 19:30
Комментарий от anik666:
Эмм $a=($b-$a)+($b=$a); и всё)
Статистика

Тестов: 153, вопросов: 8597. Пройдено: 427895 / 2095200.

Задачи / Поиск уникального значения

Автор: k06a  к списку      

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

Необходимо также предложить алгоритм, если уникальных числа два.
Ответ
Первая задача решается за один проход по массиву.
Необходимо подсчитать XOR-сумму всех чисел массива.
Таким образом пары чисел "уничтожат" друг друга (A xor A = 0).

Для решения второй задачи необходимо разбить диапазон возможных значений чисел на несколько одинаковых по размеру поддиапазонов, например строго пополам. За один проход по массиву нужно вычислять XOR-суммы в поддиапазонах по-отдельности. Далее необходимо делить на поддиапазоны, объединение тех диапазонов, где XOR-сумма получилась не ноль. Как только при подсчёте XOR-сумм найдутся 2 диапазона с ненулевой XOR-суммой, это и будут искомые значение.

Например, для однобайтовых чисел и двух поддиапазонов: после первого прохода будут посчитанны XOR-суммы чисел диапазонов 0-127 и 128-255. Таким образом, если числа были в разных диапазонах, то обе XOR-суммы окажутся ненулевыми.

Для увеличения скорости поиска нужно использовать большее число поддиапазонов. Число проходов равно O(logA(B)), где A - число поддиапазонов (ячеек памяти для хранения XOR-сумм), а B - разрядность чисел в массиве.

Если Вам понравился вопрос, проголосуйте за него

Голосов: 19  loading...
SirSlava   Deadly   xornotxor   lamed33   Ibanez   atomix   KvanGee   krazh   art   lazik234   worm2   SkyFreeLancer   Engineer9   k06a   zZoMROT   vasyura   azarov   Ingaf   doubt