Чтобы найти два уникальных числа в массиве, можно использовать различные методы. Вот несколько подходов, которые вы можете рассмотреть:
-
Использование хеш-таблицы. Перебирайте массив и сохраняйте частоту каждого числа в хеш-таблице. Затем выполните итерацию по хеш-таблице и выберите числа с частотой 1. Временная сложность этого метода равна O(n), где n — размер массива.
-
Использование битовой манипуляции: XOR всех чисел в массиве. В результате получится число, представляющее собой XOR двух уникальных чисел. Найдите самый правый установленный бит в этом результате XOR. Разделите массив на две группы: одну с числами, имеющими установленный бит в этой позиции, и другую с числами, имеющими неустановленный бит в этой позиции. Выполните операцию XOR для всех чисел в каждой группе отдельно, и вы получите два уникальных числа. Этот метод также имеет временную сложность O(n).
-
Использование сортировки: отсортируйте массив в неубывающем порядке. Переберите отсортированный массив и сравните каждое число с соседними числами. Числа, которые не равны ни одному из соседних чисел, будут уникальными числами. Этот метод имеет временную сложность O(n log n) из-за операции сортировки.
-
Использование набора: выполните итерацию по массиву и добавьте каждое число в структуру данных набора. Если номер уже присутствует в наборе, удалите его. В конце набор будет содержать два уникальных номера. Этот метод имеет временную сложность O(n), но требует дополнительного места для набора.