Arsenal911's blog

By Arsenal911, 12 years ago, In Russian

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

Массив из 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);
  • Vote: I like it
  • +25
  • Vote: I do not like it