LeetCode - разбираем задачу 136. Single Number и оптимальное решение на Swift

В этой статье мы подробно разберем задачу "Single Number" с LeetCode и покажем, как эффективно решить её на Swift. Мы рассмотрим несколько подходов и объясним, почему использование побитовой операции XOR является наилучшим решением.

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

Нужно найти этот единственный элемент.

Решение должно работать за линейное время O(n).
Нельзя использовать дополнительную память больше, чем O(1).

Вход:

let nums = [2, 2, 1]

Выход:

Вход:

let nums = [4, 1, 2, 1, 2]

Выход:

Вход:

let nums = [1]

Выход:

Один из очевидных способов — использовать словарь (Dictionary) для хранения количества вхождений каждого числа.

Код на Swift:

func singleNumber(_ nums: [Int]) -> Int { var countDict = [Int: Int]() for num in nums { countDict[num, default: 0] += 1 } for (key, value) in countDict { if value == 1 { return key } } return -1 // Этот случай никогда не наступит, так как условие гарантирует наличие одиночного элемента. }

⏳ Временная сложность: O(n)

📌 Пространственная сложность: O(n) (из-за хранения данных в словаре)

❌ Недостаток: Использует дополнительную память, что нарушает условие O(1) по памяти.

Лучший способ решения этой задачи — использование побитового XOR (^).

a ^ a = 0 (любое число, XOR с самим собой, дает 0)
a ^ 0 = a (любое число, XOR с 0, остается без изменений)
a ^ b ^ a = b (из-за коммутативности XOR порядок не важен, повторяющиеся числа исчезают)

Так как все числа в массиве встречаются дважды, кроме одного, то, применяя XOR последовательно ко всем элементам, все повторяющиеся числа обнулятся, и останется только тот самый одинокий элемент.

Код на Swift:

class Solution { func singleNumber(_ nums: [Int]) -> Int { var result = 0 for num in nums { result ^= num } return result } }

🕒 Временная сложность: O(n) (один проход по массиву)

📌 Пространственная сложность: O(1) (используется только одна переменная result)

Допустим, у нас есть входные данные:

let nums = [4, 1, 2, 1, 2]

result = 0 0 ^ 4 = 4 4 ^ 1 = 5 5 ^ 2 = 7 7 ^ 1 = 6 6 ^ 2 = 4 (остается только "4", так как 1 и 2 исчезли)

Ответ: 4 ✅

Использование словаря (O(n) памяти) — простое, но неэффективное решение.
Использование XOR (O(1) памяти) — оптимальный вариант, так как позволяет решить задачу в O(n) времени и O(1) памяти.

Если вас спросят на собеседовании, как найти уникальный элемент в массиве с дубликатами, XOR — лучший вариант! 🚀

👉 Теперь вы знаете, как решить задачу Single Number на Swift! 😎

LeetCode - разбираем задачу 136. Single Number и оптимальное решение на Swift

📌 Условие задачи

🔹 Важные условия:

🔹 Примеры

Пример 1

Пример 2

Пример 3

🔍 Рассмотрим разные способы решения

🟠 1. Наивный способ: Используем словарь (Hash Table)

🟢 2. Оптимальное решение с использованием XOR

Как работает XOR?

🔥 Разбор кода с XOR

📌 Заключение