Single Number
Дан список nums, в котором каждое значение встречается ровно дважды, кроме одного значения, которое встречается только один раз. Верните значение, которое встречается один раз.
Функция
- numsinteger-array
- список, в котором каждое значение встречается дважды, кроме одного
- Возвращаетinteger
- значение, которое встречается только один раз
Ограничения
1 ≤ nums.length < 104-104 ≤ nums[i] ≤ 104- Каждое значение встречается ровно дважды, кроме одного значения, которое встречается ровно один раз.
Примеры
- Ввод
- nums = [8, 3, 8]
- Вывод
- 3
- Пояснение
- 8 встречается дважды, а 3 — один раз, поэтому ответ — 3.
- Ввод
- nums = [5, -2, 7, 5, 7]
- Вывод
- -2
- Пояснение
- Числа 5 и 7 встречаются по два раза, а -2 — единственное значение, которое встречается один раз. Отрицательный ответ находится так же, как и положительный.
- Ввод
- nums = [42]
- Вывод
- 42
- Пояснение
- В списке с одним значением вообще нет пар, поэтому это значение и есть ответ.
+13 скрытых тестов при отправке
Дополнительный вопрос
Что, если каждое значение встречалось бы три раза, кроме одного? Один XOR уже не отменит тройки. Сможешь ли ты найти единственное значение за время O(n) и с дополнительной памятью O(1)?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Если бы можно было заставить исчезнуть каждую пару одинаковых значений, остался бы только ответ. Есть ли операция, которая превращает два одинаковых числа в ничто?
XOR обладает такими свойствами:
x ^ xравно0, аx ^ 0равноx. Порядок также не важен, поэтому две копии значения не обязательно должны располагаться рядом, чтобы взаимно сократиться.Оставь одну переменную, которая начинается с
0. Выполни XOR для каждого значения изnums, затем верни её. Ни карта, ни сортировка не нужны.
Решение
Найти значение без пары — это задача на подсчёт, и хеш-таблица подсчитывает каждое значение за один проход. Но есть нюанс: таблица растёт вместе со списком. XOR позволяет вообще не вести подсчёт, потому что XOR значения с самим собой даёт 0. Выполните XOR для всего списка, и каждая пара взаимно уничтожится, оставив единственное значение за один проход с одной переменной.
Подсчитайте каждое значение с помощью сканирования
Верно, но не успевает на самых больших тестах
Идея
По очереди берите каждое значение и просматривайте весь список, подсчитывая, сколько раз оно встречается. Значение из пары считается 2 раза. Единственное значение считается 1 раз, поэтому верните первое значение, количество вхождений которого равно 1.
Это правильно, потому что количества напрямую следуют из определения ответа, и для этого не требуется дополнительная память, кроме счётчика.
Это медленно, потому что каждое из n значений запускает полный просмотр n значений. Если единственное значение стоит в конце списка из 9,999 элементов, это почти 10^8 сравнений.
Алгоритм
- Переберите каждое значение в
nums. - Просмотрите весь список и подсчитайте значения, равные ему.
- Если количество равно 1, верните это значение.
def singleNumber(nums):
for value in nums:
# count() scans the whole list: O(n) per value.
if nums.count(value) == 1:
return value
return 0Подсчёт с помощью хеш-таблицы
Идея
Повторное сканирование списка для каждого значения приводит к лишней работе. Вместо этого подсчитайте все значения за один проход: используйте хеш-таблицу, где каждому значению соответствует количество его появлений, и на каждом шаге увеличивайте счётчик текущего значения на 1.
Для [5, -2, 7, 5, 7] в хеш-таблице в итоге будут значения 5 → 2, -2 → 1, 7 → 2. Второй проход по хеш-таблице находит запись со счётчиком 1 — это -2.
Для каждого значения требуется одно обновление хеш-таблицы, поэтому время выполнения составляет O(n). В хеш-таблице хранится около n/2 записей, что требует O(n) дополнительной памяти. В C, где нет встроенной хеш-таблицы, ту же роль выполняет массив счётчиков, индексируемый по value + 10^4, поскольку значения невелики.
Алгоритм
- Создай пустое отображение значений на их количество.
- Для каждого значения в
numsувеличивай его счётчик на 1. - Пройдись по отображению и верни значение, счётчик которого равен 1.
def singleNumber(nums):
counts = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
for value, count in counts.items():
if count == 1:
return value
return 0XOR все значения
Идея
Оператор XOR сравнивает два числа побитово и устанавливает бит там, где они различаются. Отсюда следуют три факта: x ^ x = 0, x ^ 0 = x, и порядок операций не имеет значения.
Поэтому примените XOR ко всему списку, записывая результат в одну переменную, начальное значение которой равно 0. Можно перегруппировать операции так, чтобы каждая пара встретилась со своей парой, и каждая пара даст 0. Останется 0 ^ single, то есть единственное значение. Для [8, 3, 8]: 0 ^ 8 = 8, затем 8 ^ 3 = 11, затем 11 ^ 8 = 3.
Отрицательные числа тоже подходят. XOR работает с битами представления в дополнительном коде, и у двух одинаковых отрицательных чисел биты совпадают, поэтому они взаимно уничтожаются, как и любая другая пара. Цикл считывает каждое значение один раз и использует одну переменную: время O(n) и дополнительная память O(1).
Алгоритм
- Установи
resultравным 0. - Для каждого значения в
numsустановиresultравнымresult ^ value. - Верни
result.
def singleNumber(nums):
result = 0
for value in nums:
result ^= value
return result
Ловушки и крайние случаи
Цикл XOR короткий, поэтому ошибки скрываются в том, с чего он начинается, и в альтернативных подходах.
- Начать с
result, равногоnums[0], а затем пройти циклом по каждому значению, включая индекс 0. Первое значение участвует в XOR дважды и сокращается. Начните с 0 или пропустите индекс 0. - Отсортировать значения и сравнивать соседние парами, а затем забыть, что единственное значение может оказаться последним элементом. В
[1, 1, 2]нет несовпадающей пары, а ответ — оставшаяся 2. - Использовать
2 × sum(distinct values) - sum(nums). Результат будет правильным, но множество уникальных значений требуетO(n)памяти, от которой позволяет избавиться вариант с XOR. - Ожидать, что XOR будет работать и для других количеств повторений. Он сокращает значения, встречающиеся чётное число раз. Если бы значение встретилось трижды, одна копия осталась бы и испортила ответ.
Частые вопросы4
Какова временная сложность задачи Single Number?
Решение с XOR выполняется за время O(n) и требует O(1) дополнительной памяти, потому что оно считывает каждое значение один раз и хранит одну переменную. Хеш-таблица также требует времени O(n), но ей нужна память O(n). Подсчёт каждого значения с помощью нового прохода занимает O(n²).
Почему XOR решает задачу Single Number?
Применение операции XOR к числу и самому себе даёт 0, применение XOR к числу и 0 ничего не меняет, а порядок операций не имеет значения. Поэтому, когда вы применяете XOR ко всему списку, каждую пару можно сгруппировать вместе, и она взаимно уничтожается, давая 0. Остаётся только значение без пары.
Работает ли приём с XOR с отрицательными числами?
Да. XOR работает с битами, в которых хранится число, а отрицательные числа хранятся в дополнительном коде. У двух одинаковых отрицательных чисел биты идентичны, поэтому они взаимно уничтожаются так же, как положительные. В [5, -2, 7, 5, 7] результат равен -2.
Как решить эту задачу, если остальные значения встречаются три раза?
XOR сокращает пары, но не тройки, поэтому здесь этот способ не работает. Вместо этого подсчитай, сколько значений имеют установленным каждый из 32 битов. Для каждого бита остаток от деления этого количества на 3 и будет соответствующим битом единственного значения, потому что тройки дают кратные 3. Это по-прежнему занимает время O(n) и требует O(1) дополнительной памяти.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
Python
def singleNumber(nums):
# Напишите код здесьСлучай 1
Случай 2
Случай 3
Ввод
nums = [8, 3, 8]
Ожидается
3