Блог пользователя Arsenal911

Автор Arsenal911, 12 лет назад, По-русски

Постановка задачи:

Массив из n =2k+2 элементов, 2 элемента не имеют пары, остальные парные. Найти эти 2 элемента, при условии, что алгоритм должен работать за O(n) времени и использовать O(1) дополнительной памяти.

Решение для поиска одного не повторяющего элемента:

Сначала рассмотрим задачу, когда один элемент различен. Вспомним свойство xor, применение к 2 одинаковым числа даст ноль. Следовательно если мы пропустим весь массив, то в результате у нас останется как раз искомый элемент.

int mas[] = {4,5,23,7,7,23,4,5,9};
int ans = mas[0];
for(int i = 1; i < mas.length; i++){
   ans ^= mas[i];
}
System.out.print(ans);

Решение для поиска 2 не повторяющихся элементов:

Для поиска двух элементов мы делаем сначала аналогично первому варианту, но теперь у нас в ответе пока находится xor этих двух чисел. Но если в бите установлена 1 значит в одном числе она есть, а во втором ее нет. Поэтому найдем также xor для все чисел которые имееют бит 1 в этом разряде. А второе число находится исходя из свойства xor.

int mas[] = {4,5,23,7,7,23,4,9};
int ans = mas[0];
for(int i = 1; i < mas.length; i++){
    ans ^= mas[i];
}
int tmp = 1;
Находим первый разряд в котором есть 1
while ((ans & tmp) == 0) {
    tmp *= 2;
}
int res = 0;
Находим xor для всех элементов у которых этот бит установлен в 1
for (int i = 0; i < mas.length; i++) {
     if ((mas[i] & tmp) > 0) {
         res ^= mas[i];
     }
}
System.out.println(res);
System.out.println(res ^ ans);
  • Проголосовать: нравится
  • +25
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Подобные "фокусы" очень хорошо с примерами описаны здесь.

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Вы не могли бы объяснить, почему для 2х чисел мы находим первый ненулевой бит и после пробега по массиву мы получаем ответ?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Т.к. при xor'е всех чисел у которых i-й бит — 1 некоторые пары одинаковых чисел попадут сюда, а некоторые нет, в любом случае их xor будет равен нулю, но при этом в это выражение попадет лишь одно из непарных чисел и следственно результат — то непарное число в котором и был единичный бит в i-й позиции.

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

О, а вот такой вопрос. Как откатить ввод? Просто если у нас жесткое ограничение по памяти, то хранить массив — не вариант. Именно эта проблема и была тогда на KPI-Open: если для решения нужно более одного раза пройти по массиву, то нужно откатывать ввод. Не подскажете, как это сделать?

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Решал эту задачу при помощи freopen (или повторного freopen).

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    Не нужно откатывать ввод. Можно просто хранить массив на 32 элемента. Когда приходит новое число нам надо найти позиции в этом числе где находятся единички в двоичном представлении. Потом проксорить это число с соответствующими значениями в этих позициях в массиве. Фактически теперь мы имеем значения xor чисел у которых в соответствующих битах стоят единички. А далее по алгоритму.