Самый быстрый способ найти уникальные элементы из заданных номеров

Question

у меня есть n номеров.n <= 1000000. Каждое число будет положительным целым числом и будет меньше 10 ^ 9. </p>

Уверен, что один раз будет только одно число, покой будет дважды или даже несколько раз.

Самое короткое из известных мне решений - результат XOR всех чисел.Я хочу знать

• Какова будет сложность стандартного решения XOR.
• Как мы можем оптимизировать решение.

Answer 1

XOR для всех чисел будет иметь сложность O (n), так как вам нужно будет посетить каждый элемент только один раз.,XOR - очень дешевая операция, и природа проблемы требует, чтобы вы посещали каждый элемент хотя бы один раз: в противном случае вы не сможете узнать, какое значение является уникальным.

Answer 2

Алгоритм XOR является правильным и самым быстрым.Медленная часть - это способ, которым вы читаете ввод.

Например, scanf в C медленнее, чем ручное управление вашим собственным алгоритмом чисел с помощью getchar (или даже лучше getchar_unlocked).В проблеме SPOJ, о которой вы упомянули, я получил улучшение с 1,35 до 0,14 с, просто внеся это изменение.Я уверен, что оставшиеся 0,04, чтобы получить лучшее время на сайте, просто из-за лучшего ввода-вывода низкого уровня, чем мой код.

Answer 3

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