Single Number

Лёгкая№136xor

Дан массив целых чисел, где каждое число встречается ровно дважды, кроме одного, которое встречается один раз. Нужно найти его за один проход и O(1) дополнительной памяти. Наш пример: [10, 3, 7, 3, 10] — ответ 7.

136 Single NumberРазбор · 1×

Пример: [10, 3, 7, 3, 10]. Под массивом — num и result в двоичной записи; переключённые биты result подсвечены.

0101327334108421вес разрядаnum—result0000= 0
ещё не дошли; бит 0текущее число; бит, который только что переключилсяуже в result, пара ещё не встретилась; бит 1 в resultбит 1 в num: он переключает resultпара, которая сократиласьчисло без пары

result начинается с 0 = 0000: он ничего не меняет в xor

01/13
сначала · назад · пуск · шаг
Скорость
1function singleNumber(nums):
2 result = 0
3 for each num in nums:
4 result = result xor num
5 return result
состояние
result
0 = 0000
num
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. xor переключает каждый бит result там, где в num стоит 1. Число, пришедшее дважды, переключает одни и те же биты два раза, и они возвращаются: a xor a = 0, а x xor 0 = x.
  2. Переключениям не важен порядок: две 10 стоят далеко друг от друга, а между ними result проходит 9, 14 и 13 — числа, которых в массиве нет. Важен только итог.
  3. После всех чисел бит result равен 1 ровно тогда, когда 1 в этом месте была у нечётного числа чисел. Пары дают везде чётное число, поэтому остаются биты числа без пары.

Сложность

Время O(n): один проход, по одному xor на число. Память O(1): одно число, без множества и словаря.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.