Single Number II

Средняя№137по битам

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

137 Single Number IIРазбор · 1×

Пример: [3, 5, 3, 6, 5, 3, 5], width = 3. Столбец под числом — его биты; справа — сколько единиц в строке бита.

nums3536535onesбит 20101101бит 11011010бит 01110111answer000= 0
бит 0бит 1читаемый битуже посчитанная 1; счёт на этот моментсчёт, кратный 3бит ответа; число без тройки

answer начинается с 000: его биты ставятся по одному столбцу

01/55
сначала · назад · пуск · шаг
Скорость
1function singleNumber(nums, width):
2 answer = 0
3 for b from 0 to width - 1:
4 ones = 0
5 for each num in nums:
6 ones = ones + ((num >> b) & 1)
7 if ones % 3 == 1:
8 answer = answer | (1 << b)
9 return answer
состояние
answer
0 = 000
b
–
ones
–
num
–
историянажмите шаг, чтобы вернуться

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

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

  1. Посмотрим на одну позицию бита. Каждое число из тройки даёт там 0 или 3 единицы, так что тройки вместе дают число, кратное 3. Число без тройки добавляет сверху 1 или 0, и ones % 3 показывает, что именно.
  2. Биты не смешиваются: каждая позиция считается отдельно, и позиции, где ones % 3 = 1, — ровно единичные биты ответа. В столбце 0 две тройки дают 6 единиц, а 6 % 3 = 0.
  3. Обычный xor здесь не работает: три копии числа переключают его биты три раза и оставляют одну копию. Здесь xor всех чисел равен 0, а не 6.

Сложность

Время O(w · n), где w — ширина: по проходу по числам на каждый бит, на LeetCode w = 32, то есть O(n). Память O(1): счётчик и ответ.

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

Решить на LeetCode ↗

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