Старое, но золотое

Старое, но золотое

Давайте обсудим задачу программирования. У вас есть куча числовых пар, например 5, 5, 7, 7, 2, 2 и одно уникальное число, например 13. Вы смешиваете все в один массив и перетасовываете его. Теперь у вас есть что-то вроде [7, 2, 13, 5, 2, 7, 5]. Пусть n — количество элементов, и пусть оно будет огромным, например 100000000. Числа имеют ширину 32 или 64 бита. Задача — найти уникальный номер. В нашем случае это будет 13.

Не стесняйтесь поделиться в комментариях временной и памятью сложностью вашего подхода, например: T=O(...); M=O(...).

Думаю, было бы интересно за несколько дней собрать варианты, а потом сравнить алгоритмы.