Имеется массив натуральных чисел. Каждое из чисел присутствует в массиве ровно два раза и только одно из чисел не имеет пары. Необходимо предложить алгоритм, чтобы за минимальное число проходов по массиву определял число не имеющее пары.
Необходимо также предложить алгоритм, если уникальных числа два.
Для пользователей, которые регистрируются. Если Вам не приходит письмо с подтверждением email, пишите на admin[at]quizful[dot]net - будем подтверждать вручную. Просим прощения за доставленные неудобства.
С уважением,
команда Quizful
С уважением,
команда Quizful
Знаете ли Вы, что
В разделе "Статьи" можно найти обучающие статьи по информационным технологиям, а также узнать о новостях сервиса Quizful.
←
→
Топ контрибуторов
←
→
Лента обновлений
|
ссылка
May 17 19:13
Комментарий от elirijndael: Полностью согласен с valid_name. |
|
ссылка
May 17 18:47
Комментарий от Aleksandr89: Неплохой тест. Для тех кто хочет ещё попрактиковатьс... |
|
ссылка
May 17 15:13
Комментарий от dpdpdp: Поменяйте радиокнопки на чекбоксы. Во втором варианте про... |
|
ссылка
May 17 11:55
Комментарий от Torredo812: вот это подвох!!! забываешь что х увеличился))и думае... |
|
ссылка
May 17 10:50
Комментарий от lesha1980: Хороший вопрос. Получается, что проверяется только x в... |
Статистика
Тестов: 130, вопросов: 5791. Пройдено: 126756 / 526576.
Поиск уникального значения
← к списку ← →
Вопрос
Ответ
Первая задача решается за один проход по массиву.
Необходимо подсчитать XOR-сумму всех чисел массива.
Таким образом пары чисел "уничтожат" друг друга (A xor A = 0).
Необходимо подсчитать XOR-сумму всех чисел массива.
Таким образом пары чисел "уничтожат" друг друга (A xor A = 0).
Для решения второй задачи необходимо разбить диапазон возможных значений чисел на несколько одинаковых по размеру поддиапазонов, например строго пополам. За один проход по массиву нужно вычислять XOR-суммы в поддиапазонах по-отдельности. Далее необходимо делить на поддиапазоны, объединение тех диапазонов, где XOR-сумма получилась не ноль. Как только при подсчёте XOR-сумм найдутся 2 диапазона с ненулевой XOR-суммой, это и будут искомые значение.
Например, для однобайтовых чисел и двух поддиапазонов: после первого прохода будут посчитанны XOR-суммы чисел диапазонов 0-127 и 128-255. Таким образом, если числа были в разных диапазонах, то обе XOR-суммы окажутся ненулевыми.
Для увеличения скорости поиска нужно использовать большее число поддиапазонов. Число проходов равно O(logA(B)), где A - число поддиапазонов (ячеек памяти для хранения XOR-сумм), а B - разрядность чисел в массиве.
