Найти число, встречающееся один раз, когда все остальные встречаются дважды
Дан непустой массив целых чисел, где каждый элемент встречается ровно дважды, кроме одного. Верните этот единственный элемент. Требования: O(n) по времени и O(1) дополнительной памяти — хеш-подсчёт вхождений использует O(n) памяти и является базовым решением, которое нужно превзойти.
function singleNumber(nums) {
// ваш код здесь
}Допишите реализацию.
Сложите все элементы по XOR — nums.reduce((a, b) => a ^ b, 0). XOR коммутативен и ассоциативен, x ^ x === 0, а x ^ 0 === x, поэтому каждая пара сокращается до нуля и выживает только одиночное значение. Это O(n) по времени и O(1) по памяти, что превосходит базовый хеш-подсчёт, требующий O(n) памяти.
- ✗Хвататься за хеш-таблицу или подсчёт через
Set, что решает задачу, но за O(n) памяти - ✗Забывать, что нейтральный элемент XOR —
0, поэтому reduce должен стартовать с0 - ✗Считать, что XOR работает только на отсортированном входе — порядок ему не важен
- →Как изменится подход с XOR, если каждый прочий элемент встречался бы трижды?
- →Почему старт
reduceс0, а не сnums[0], сохраняет код корректным?
Решение
XOR всех элементов сокращает все пары и оставляет одиночное значение.
function singleNumber(nums) {
return nums.reduce((acc, n) => acc ^ n, 0);
}Как это работает
XOR обладает тремя свойствами: он коммутативен и ассоциативен (порядок не важен), x ^ x === 0 (одинаковые значения сокращаются), и x ^ 0 === x (0 — нейтральный элемент). Поэтому, складывая по XOR весь массив, каждая пара дубликатов превращается в 0, а оставшееся одиночное число «выживает».
Проход ровно один — O(n) по времени, и хранится один аккумулятор — O(1) по памяти. Базовое решение с подсчётом в хеш-таблице тоже даёт O(n) по времени, но платит O(n) памятью.
