JuniorКодОчень частоЕщё не отвечали
Найдите уникальный элемент в массиве, где все остальные встречаются дважды
В массиве целых чисел каждый элемент встречается ровно дважды, кроме одного. Верните этот единственный уникальный элемент.
Требования:
и без сортировки.
- O(n) время, O(1) дополнительной памяти, один проход — без хеш-таблицы
- Не изменяйте входной массив.
int findUnique(const std::vector<int>& nums) {
// ваш код здесь
}Допишите реализацию.
Применить XOR ко всем элементам. Пары взаимно уничтожаются (a XOR a = 0), в результате остаётся единственный непарный элемент. Время O(n), память O(1), один проход.
- ✗Использовать хеш-таблицу — O(n) память излишня, когда XOR даёт O(1)
- ✗Сортировать массив — O(n log n) и изменяет входные данные
- ✗Не обобщать: это работает только когда ровно один элемент встречается нечётное число раз
- →Как найти два уникальных элемента, когда все остальные встречаются дважды?
- →Как найти уникальный элемент, когда все остальные встречаются трижды?
Оглавление
Задача
В массиве целых чисел все элементы встречаются ровно дважды, кроме одного. Найдите этот элемент за O(n) времени и O(1) памяти.
Решение
#include <vector>
#include <cassert>
// XOR всех элементов — пары обнуляются, остаётся уникальный
int findUnique(const std::vector<int>& nums) {
int result = 0;
for (int x : nums) result ^= x;
return result;
}
int main() {
assert(findUnique({2, 2, 1}) == 1);
assert(findUnique({4, 1, 2, 1, 2}) == 4);
assert(findUnique({1}) == 1);
assert(findUnique({0, 1, 0}) == 1);
}Ключевые моменты
a XOR a = 0,a XOR 0 = a— ключевые свойства.- Порядок элементов не имеет значения — XOR коммутативен и ассоциативен.
- Работает за один проход без дополнительной памяти.
- Обобщение: если нужно найти два уникальных элемента, используйте XOR + разбиение по группам.
Оглавление
