Алгоритм нахождения чисел без пар из большого потока данных?

Добрый день!

Сегодня проходила олимпиада KPI-Open и на ней была интересная задача:

Ограничения: 8 сек. 8Мб

Условие

Есть N натуральных чисел ( N парное от 2 до 10 000 000) по модулю не больше 1 000 000 000. Среди этих чисел почти все имеют себе пару. Но два числа — без пары. Необходимо найти те самые два числа без пары.

Внимание обращаю на ограничения.

Пример

На вход

6

4 8 4 7 9 9

Ответ

7 8



Пример2

На вход

8

7 7 7 5 5 5 5 6

Ответ

6 7




Решение с BitMap не проходит по памяти. Содержать все числа в памяти не получается. Думаем, что решение основывается на xor-е всех чисел между собой и подбором двух чисел, которые бы при xor-е их с хоr-ом всех чисел дали бы 0.

Дело в том, что для xor подойдут не исключительно два числа — а некоторый набор. Для того что бы отсеять неподходящие, скорее всего, необходимо ввести правило для проверки. Возможно есть возможность узнать сумму этих чисел(которые без пары) или их произведение?
  • Вопрос задан
  • 8220 просмотров
Решения вопроса 1
jcmvbkbc
@jcmvbkbc
http://dilbert.com/strip/1998-08-24
uint32_t xor_all = 0;
uint32_t xor_bit[32] = {0};

....

for (i = 0; i < n; ++i) {
    xor_all ^= in;
    for (j = 0; j < 32; ++j) {
        if (in & (1 << j))
            xor_bit[j] ^= in;
    }
}

for (j = 0; j < 32; ++j) {
    if (xor_all & (1 << j)) {
        out1 = xor_bit[j];
        out2 = xor_all ^ xor_bit[j];
        break;
    }
}



Идея в том, что непарные числа должны различаться хотя бы одним битом.
Мы будем кроме общего ксора тащить по одному ксору для чисел, имеющих i-й бит установленным.
В конце общий ксор даст нам различающиеся биты, по одному из которых мы найдём одно из непарных чисел, а там и второе.
Ответ написан
Пригласить эксперта
Ответы на вопрос 3
turboNOMAD
@turboNOMAD
Я бы использовал множество (set).
Алгоритм такой: для каждого числа проверяем, есть ли оно в множестве. Если нет, добавляем, иначе удаляем. Проверка эта идет за O(log n) для std::set на C++, или вообще за константу для хэш-контейнеров. (Я не знаю, какой язык можно использовать по условию задачи).
Единственная проблема — если числа и их пары расположены не псевдослучайно, а например сначала все уникальные, а потом все их пары. В таком случае при проходе первой половины массива размер множества будет только увеличиваться и можем пролететь с ограничением по памяти.
Ответ написан
@nicolausYes
+1, писал то же самое. В зависимости от компилятора, на С++ можно использовать либо С++11 контейнеры (unordered_set), либо из пространства имен tr1 на более старых компиляторах, если такое присутствует. По сути, при решении в лоб, придется хранить как минимум половину значений, либо хранить как-то более хитро.

Чуть подумал: проблему с памятью можно обойти, если разрешено обходить числа не последовательно, а в случайном порядке.
Также можно воспрользоваться принципом «разделяй и властвуй», т.е. строить вышеописанным способом множества элементов без пары для небольших кусков исходного массива, а потом искать симметрическую разность (объединение без пересечения) этих множеств.

Так вы еще их в массив сохраняете? Сразу сохраняйте в используемую структуру при считывании (set, unordered_set, unordered_map — в tr1 точно есть).
Ответ написан
Arktos
@Arktos
Нам нужно будет считать этот массив 2 или 3 раза. Сначала будем хранить эти числа по модулю 10^5. Заведем bool-массив из 10^5 элементов — сколько раз каждый модуль встречался. Рассмотрим 2 варианта
1) Искомые числа по модулю 10^5 различные. Тогда у нас будут 2 ненулевые ячейки. Мы знаем модули искомых чисел по 10^5. Задача свелась к следующей — найти из массива чисел одно число, не имеющее себе пары. Решается xor-ом. Считываем снова массив и вычисляем 2 xor-а для найденных модулей.
2) Искомые числа равны по модулю 10^5 (все ячейки нулевые). Тогда они не равны по модулю 10^5+1.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы