Что нового
  • Что бы вступить в ряды "Принятый кодер" Вам нужно:
    Написать 10 полезных сообщений или тем и Получить 10 симпатий.
    Для того кто не хочет терять время,может пожертвовать средства для поддержки сервеса, и вступить в ряды VIP на месяц, дополнительная информация в лс.

  • Пользаватели которые будут спамить, уходят в бан без предупреждения. Спам сообщения определяется администрацией и модератором.

  • Гость, Что бы Вы хотели увидеть на нашем Форуме? Изложить свои идеи и пожелания по улучшению форума Вы можете поделиться с нами здесь. ----> Перейдите сюда
  • Все пользователи не прошедшие проверку электронной почты будут заблокированы. Все вопросы с разблокировкой обращайтесь по адресу электронной почте : info@guardianelinks.com . Не пришло сообщение о проверке или о сбросе также сообщите нам.

Найти Три Числа, Которые Встречаются В Массиве По Одному Разу, При Условии, Что Все Другие...

Sascha

Заместитель Администратора
Команда форума
Администратор
Регистрация
9 Май 2015
Сообщения
1,071
Баллы
155
Возраст
51
Пусть у нас есть массив положительных чисел, в котором все числа, кроме трех, встречаются по 2 раза, а эти три числа отличны от всех остальных и встречается каждое ровно по одному разу. Нужно найти эти три числа. Числа помещаются в 32-битный целочисленный тип.

Решение


Сделаем

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.

всех чисел, обозначим это число через x. Очевидно, что в итоге мы получим xor искомых трех чисел, так как остальные попарно сократятся (xor с сами собой — это ноль, а xor с нулем — это само число).

Рассмотрим побитовое представление числа x. Очевидно, что найдется хотя бы один такой бит, в котором одно из трех чисел отличается от двух других (иначе эти три числа были бы равными). Будем перебирать биты этого числа в некотором порядке. Пусть i-й бит числа равен 1. Тогда возможны два варианта: либо у одного из трех искомых чисел в этом бите 1, а у других 0, либо у всех 1.

В 1-м случае мы сможем выделить одно из трех чисел. Сделаем xor всех чисел массива у которых в i-м бите также 1, обозначим это число через y. Очевидно, что числа не входящие в искомые три числа сократятся, то есть мы получим xor тех чисел, которые входят в наши три числа, и у которых при этом в i-м бите 1. Если x = y, то реализовался второй случай, иначе первый случай.

В случае если i-й бит числа x равен 0, поступаем полностью аналогично. В этом случае у нас будут варианты: либо у всех трех чисел i-й бит 0, либо у одного числа i-й бит 0, а у двух других 1. Аналогично находим xor всех чисел у которых в i-м бите 0 и если мы получили число не равное x, то мы выделили одно из трех чисел.

Так как хотя бы в одном бите одно из трех чисел будет отличаться от остальных двух, то мы точно сможем выделить одно из чисел. Далее находим xor двух оставшихся чисел, для этого xor’им x с выделенным числом. Задача свелась к такой же, только в ней вместо трех чисел — два, каждое встречается по одному разу, выделенное ранее третье число больше нигде не будем учитывать. Одно из двух чисел выделяется аналогично, при этом не нужно перебирать биты, которые мы уже перебрали, когда выделяли первое число, так как оставшиеся два числа в них совпадают, иначе бы мы выделили одно из них.

Со свойствами битовых операций можете ознакомиться в

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.

.


Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.

.
 
Вверх