Как решить задачу Single Number c LeetCode
https://leetcode.com/problems/single-number/
Задача Single Number является одной из классических задач программирования, встречающихся на собеседованиях и соревнованиях. Она помогает оценить понимание основ битовых операций и алгоритмов. Давайте разберемся, как её эффективно решить.
Условие задачи
Дан массив целых чисел nums, каждый элемент которого повторяется дважды, кроме одного числа, которое встречается ровно один раз. Необходимо вернуть это единственное число.
Пример:
Input: nums = [4,1,2,1,2]
Output: 4
Подход №1: Использование множества (Set)
Простое решение состоит в том, чтобы создать множество и добавить туда элементы массива. Если элемент уже присутствует в множестве, удаляем его. В конце останется одно уникальное значение.
def singleNumber(nums):
seen = set()
for num in nums:
if num in seen:
seen.remove(num)
else:
seen.add(num)
return list(seen)[0]
Однако этот метод требует дополнительной памяти для хранения множества.
Оптимальное решение: Битовые операции XOR (https://ru.wikipedia.org/wiki/Исключающее_«или»)
Более элегантное и эффективное решение заключается в использовании оператора исключающего “ИЛИ” (XOR). Основное свойство XOR в данном контексте:
- Любое число XOR само себе равно нулю: a⊕a=0
- Ноль XOR любое число даёт само число: 0⊕a=a
Таким образом, если мы пройдем по всему массиву и применим операцию XOR ко всем числам, все пары взаимно уничтожатся, оставив лишь искомое число.
def singleNumber(nums):
result = 0
for num in nums:
result ^= num
return result
Этот алгоритм работает за линейное время (O(n)) и использует константную память (O(1)).
Анализ решения
| Метод | Время выполнения | Пространственная сложность |
|---|---|---|
| Set | O(n) | O(n) |
| XOR | O(n) | O(1) |
Оптимальным решением является использование XOR, поскольку оно минимизирует расходуемые ресурсы и сохраняет простоту реализации.
Эта задача показывает важность понимания базовых принципов работы битов и демонстрирует силу простых операций над ними. Решение позволяет значительно оптимизировать код и сделать его эффективным даже для больших объемов данных.
