четверг, 1 апреля 2010 г.

Задачка про уникальность

1. Имеется массив чисел конечной длины. Все числа в нём присутствуют ровно в двух экземплярах. И лишь одно число присутствует в единственном экземпляре. Необходимо за минимальное(конечное) число проходов по массиву определить значение этого уникального числа.

2. Решить ту же задачу, только теперь имеется два уникальных числа.

(Задачку позаимствовал у Смола)

UPD: Александр, на память ограничения не накладываются. Желательно использовать разумное количество памяти. Может получиться, например, прямая зависимость между используемой памятью и сложностью алгоритма(число операций), тогда это стоит отдельно обговорить в ответе.

UPD_2: Для поиска одного из чисел используется операция XOR для всех элементов массива. В результате пары элементов дадут нули, а уникальное число останется в результате.

Для поиска 2-х числе необходимо использовать следующий алгоритм:

При первом проходе считать 2 различных XOR-а, в один складывать числа большие 0x80000000, а в другой - меньшие.

Если обе XOR-суммы не равны нулю, то оба XOR-а равны соответствующим уникальным числам.

Если один из XOR-ов равен нулю, то диапазон на котором XOR не равен нулю снова делится пополам.

В результате число проходов пропорционально логарифму разрядности чисел, то есть O(log2(sizeof(n))).

17 комментариев:

Pushkoff комментирует...

Это из теста на С++ программиста в Gameloft...

Александр комментирует...

Дополнительнию память можно использовать?

[k06a] комментирует...

Александр, на память ограничения не накладываются. Желательно использовать разумное количество памяти. Может получиться, например, прямая зависимость между используемой памятью и сложностью алгоритма(число операций), тогда это стоит отдельно обговорить в ответе.

Александр комментирует...

Если сами числа совершенно произвольные (например, даже дробные) и их не получается использовать как-то хитро как индексы массива-карты или как ключи хеш-таблицы обработанных элементов со временем доступа O(1), то остается только отсортировать массив - это время O(N*log(N)), а потом его линейно пробежать, проверяя, что каждый элемент имеет рядом равную ему пару. Это будет время O(N), то есть в этоге будет O(N*log(N)). Тут уже не важно, сколько уникальных элементов искать.

Но это все весьма прямолинейно. Забавно, если задачу можно решить просто в один проход.

[k06a] комментирует...

Александр, для упрощения можно считать, что разрядность чисел в массиве не превышаеть разрядности операционной системы и уж тем более разрядности процессора. Пусть это будут беззнаковые 32-хразрядные целые числа.

Александр комментирует...

Для поиска одного числа:

int a[] = { 20, 31, 20, 1, 3, 1, 3, 40, 40, 50, 50 };

int main() {
  int i, c = 0;
  for (i = 0; i < sizeof(a)/sizeof(*a); ++i)
    c ^= a[i];
  printf("%d\n", c);
}

Выводит: 31

Для двух надо подумать еще ;-).

[k06a] комментирует...

Существует решение, находящее ответ за константное число проходов. Тоесть сложность O(n).

[k06a] комментирует...

Ой, это я про одно уникальное число.
Для двух чисел зависимость логарифмическая.

Александр комментирует...

Так мое решение с xor для одного числа подходит?

[k06a] комментирует...

Лучше ксора я тоже ничего не придумал на первое задание. Так что думаю это и есть верный ответ. Второе задание поинтересней))

[k06a] комментирует...

Что-то у меня уже глюки)) Пару сообщений назад про логарифм сбредил. У второго алгоритма получил сложность O(n).

[k06a] комментирует...

Прошло достаточно времени.
Опубликую своё решение второй задачи.

Александр комментирует...

Красиво.

[k06a] комментирует...

Это соответственно если использовать всего 2 переменных для подсчёта XOR-суммы. На самом деле число сумм задаёт основание логарифма. Так что лучше использовать побольше))

Александр комментирует...

Так что делать, если переменных три? понять, что число?

[k06a] комментирует...

Ну, например, переменных четыре))
Тогда на первом этапе XOR-им в них диапазоны:
0x00000000 - 0x3FFFFFFFF
0x40000000 - 0x7FFFFFFFF
0x80000000 - 0xDFFFFFFFF
0xC0000000 - 0xFFFFFFFFF
В случае успеха 2 из XOR-ов будут ненулевыми.

[k06a] комментирует...

Или вы имели ввиду поиск трёх уникальных значений?

Тогда надо разбивать на диапазоны, пока не выявится 3 диапазона с ненулевой XOR-суммой.