Single Number

Q: Какова временная сложность задачи Single Number?

Решение с XOR выполняется за время O(n) и требует O(1) дополнительной памяти, потому что оно считывает каждое значение один раз и хранит одну переменную. Хеш-таблица также требует времени O(n) , но ей нужна память O(n) . Подсчёт каждого значения с помощью нового прохода занимает O(n²) .

Q: Почему XOR решает задачу Single Number?

Применение операции XOR к числу и самому себе даёт 0, применение XOR к числу и 0 ничего не меняет, а порядок операций не имеет значения. Поэтому, когда вы применяете XOR ко всему списку, каждую пару можно сгруппировать вместе, и она взаимно уничтожается, давая 0. Остаётся только значение без пары.

Q: Работает ли приём с XOR с отрицательными числами?

Да. XOR работает с битами, в которых хранится число, а отрицательные числа хранятся в дополнительном коде. У двух одинаковых отрицательных чисел биты идентичны, поэтому они взаимно уничтожаются так же, как положительные. В [5, -2, 7, 5, 7] результат равен -2.

ЛегкоБитовые операции

+10

Дан список nums, в котором каждое значение встречается ровно дважды, кроме одного значения, которое встречается только один раз. Верните значение, которое встречается один раз.

Функция

singleNumber(nums: integer-array) → integer

numsinteger-array: список, в котором каждое значение встречается дважды, кроме одного
Возвращаетinteger: значение, которое встречается только один раз

Ограничения

1 ≤ nums.length < 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
Каждое значение встречается ровно дважды, кроме одного значения, которое встречается ровно один раз.

Примеры

Ввод: nums = [8, 3, 8]
Вывод: 3
Пояснение: 8 встречается дважды, а 3 — один раз, поэтому ответ — 3.

Дополнительный вопрос

Что, если каждое значение встречалось бы три раза, кроме одного? Один XOR уже не отменит тройки. Сможешь ли ты найти единственное значение за время O(n) и с дополнительной памятью O(1)?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Найти значение без пары — это задача на подсчёт, и хеш-таблица подсчитывает каждое значение за один проход. Но есть нюанс: таблица растёт вместе со списком. 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 0

XOR все значения

Идея

Оператор 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 будет работать и для других количеств повторений. Он сокращает значения, встречающиеся чётное число раз. Если бы значение встретилось трижды, одна копия осталась бы и испортила ответ.

Частые вопросы3

Какова временная сложность задачи 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.

def singleNumber(nums):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

nums = [8, 3, 8]

Ожидаемый вывод

Single Number

Функция

Ограничения

Примеры

Подсказки

Решение

Подсчитайте каждое значение с помощью сканирования

Подсчёт с помощью хеш-таблицы

XOR все значения

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи