Найти уникальный элемент в массиве

Решение: Найти уникальный элемент в массиве

Проблема и подход

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

Почему XOR работает?

Операция XOR (исключающее ИЛИ) имеет уникальное свойство:

• a ^ a = 0 (число XOR с самим собой равно нулю)
• a ^ 0 = a (число XOR с нулём равно самому числу)
• a ^ b = b ^ a (XOR коммутативна)
• (a ^ b) ^ c = a ^ (b ^ c) (XOR ассоциативна)

Поэтому если XOR-ить все числа массива, все пары исчезнут (станут 0), и останется только уникальное число.

Оптимальное решение с XOR

function findUnique(arr) {
  return arr.reduce((result, num) => result ^ num, 0);
}

Развёрнутая версия с пояснениями

function findUnique(arr) {
  let unique = 0;
  
  for (let num of arr) {
    // XOR текущего числа с накопленным результатом
    unique ^= num;
  }
  
  return unique;
}

Пошаговый разбор примера

// Пример: [4, 1, 2, 1, 2]
// Инициализация: result = 0
// Итерация 1: 0 ^ 4 = 4
// Итерация 2: 4 ^ 1 = 5
// Итерация 3: 5 ^ 2 = 7
// Итерация 4: 7 ^ 1 = 6 (1 в третий раз, но 2 раза в паре)
// Итерация 5: 6 ^ 2 = 4 (теперь 2 тоже в паре)
// Результат: 4

// Более ясное объяснение в двоичном коде для [2, 2, 1]:
// 0    = 00
// 0^2  = 10 (2 в двоичном)
// 10^2 = 00 (2 исчезла)
// 00^1 = 01 (1 остался)
// Результат: 1

TypeScript версия

function findUnique(arr: number[]): number {
  return arr.reduce((unique: number, num: number) => unique ^ num, 0);
}

Альтернативный подход с Map (O(n) пространство)

function findUnique(arr) {
  const count = new Map();
  
  // Подсчитываем количество каждого числа
  for (let num of arr) {
    count.set(num, (count.get(num) || 0) + 1);
  }
  
  // Ищем число с количеством 1
  for (let [num, cnt] of count) {
    if (cnt === 1) return num;
  }
}

Альтернативный подход с Set (O(n) пространство)

function findUnique(arr) {
  const seen = new Set();
  
  for (let num of arr) {
    if (seen.has(num)) {
      seen.delete(num);
    } else {
      seen.add(num);
    }
  }
  
  // В Set остаётся одно число
  return Array.from(seen)[0];
}

Примеры использования

// Базовые примеры
console.log(findUnique([2, 2, 1]));                // 1
console.log(findUnique([4, 1, 2, 1, 2]));          // 4
console.log(findUnique([1]));                       // 1
console.log(findUnique([7, 3, 5, 3, 5, 7, 9]));   // 9

// Дополнительные тесты
console.log(findUnique([0]));                       // 0
console.log(findUnique([1, 1, 2, 2, 3]));          // 3
console.log(findUnique([10, 20, 10, 20, 30]));     // 30
console.log(findUnique([-1, -1, 2, 2, 5]));        // 5

Сравнение подходов

Почему XOR лучше?

// Для массива из 1 000 000 чисел:
// XOR решение:
// - Временная: O(n) = ~1,000,000 операций
// - Пространственная: O(1) = одно целое число

// Map решение:
// - Временная: O(n) = ~1,000,000 операций
// - Пространственная: O(n/2) = ~500,000 записей в памяти

Интуитивное объяснение XOR

Думай о XOR как о переключателе:

• Первое включение: цвет тёмный (0 XOR 1 = 1)
• Второе включение: цвет светлый (1 XOR 1 = 0)

Так как каждое число включается ровно дважды (кроме уникального), все переключатели возвращаются в исходное состояние (0), оставляя только уникальный.

Ключевые моменты

• Идемпотентность: a ^ a = 0 — основное свойство
• Нейтральный элемент: 0 для XOR
• Коммутативность: порядок не важен
• Ассоциативность: скобки не важны
• Для других случаев: если числа повторяются 3 раза, нужны биты счётчика