Постановка задачи:
Массив из 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);
Подобные "фокусы" очень хорошо с примерами описаны здесь.
Вы не могли бы объяснить, почему для 2х чисел мы находим первый ненулевой бит и после пробега по массиву мы получаем ответ?
Т.к. при xor'е всех чисел у которых i-й бит — 1 некоторые пары одинаковых чисел попадут сюда, а некоторые нет, в любом случае их xor будет равен нулю, но при этом в это выражение попадет лишь одно из непарных чисел и следственно результат — то непарное число в котором и был единичный бит в i-й позиции.
Задача "Носки"
О, а вот такой вопрос. Как откатить ввод? Просто если у нас жесткое ограничение по памяти, то хранить массив — не вариант. Именно эта проблема и была тогда на KPI-Open: если для решения нужно более одного раза пройти по массиву, то нужно откатывать ввод. Не подскажете, как это сделать?
seekg
fsetpos
Решал эту задачу при помощи freopen (или повторного freopen).
Не нужно откатывать ввод. Можно просто хранить массив на 32 элемента. Когда приходит новое число нам надо найти позиции в этом числе где находятся единички в двоичном представлении. Потом проксорить это число с соответствующими значениями в этих позициях в массиве. Фактически теперь мы имеем значения xor чисел у которых в соответствующих битах стоят единички. А далее по алгоритму.