Неповторяющееся число

Легкая

easy , array , bit manipulation

10 January 2024

Описание задачи #

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

Вы должны реализовать решение с линейной сложностью по времени и константной по памяти.

Ограничения #

В массиве может быть от 1 до 3 * 10⁴ элементов
Каждый элемент массива имеет значение в диапазоне от -3 * 10⁴ до 3 * 10⁴
Каждый элемент массива встречается дважды, за исключением одного элемента

Примеры #

Входные данные: [2, 2, 1]

Ответ: 1
Входные данные: [4, 1, 2, 1, 2]

Ответ: 4
Входные данные: [1]

Ответ: 1

Решение через хеш-таблицу #

Первая идея, которая может прийти в голову — реализовать классический обход массива с подсчетом частоты каждого числа. Для этого для каждого числа в хеш-таблице мы будем хранить пару, в которой ключом является само число, а значением — сколько раз оно встречается в массиве. В конце нужно будет лишь просмотреть всю таблицу и выбрать то число, у которого счетчик равен 1.

Получим такое решение.

package single_number

func singleNumberMap(nums []int) int {
	countMap := make(map[int]int)

	for _, num := range nums {
		countMap[num] += 1
	}

	for num, count := range countMap {
		if count == 1 {
			return num
		}
	}

	return 0
}

export const singleNumberMap = (nums: number[]): number => {
    const countMap: Record<number, number> = {}

    nums.forEach((num) => {
        const curr = countMap[num] ?? 0
        countMap[num] = curr + 1
    })

    const entries = Object.entries(countMap)

    for (let i = 0; i < entries.length; i++) {
        const [num, count] = entries[i]
        if (count === 1) {
            return Number(num)
        }
    }

    return 0
}

Однако, такое решение нам не подойдет, потому что использование хеш-таблицы для хранения частот приведет к тому, что у нас будет линейная сложность по памяти.

Решение через XOR #

На самом деле задача очень легкая, но надо знать хитрость, а именно — как работает операция XOR.

XOR — логическая операция исключающего или (обозначается знаком ⊕) и у нее есть несколько полезных свойств, которые мы можем использовать.

a ⊕ a = 0 — применение исключающего или к одинаковым битам в результате дает ноль.
b ⊕ 0 = b — если один из битов равен 0, то результатом вычисления будет другой бит.
a ⊕ b ⊕ a = a ⊕ a ⊕ b — операция XOR коммутативна, то есть мы можем менять порядок применения.

Исходя из этого мы можем вывести простое решение.

a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b

То есть, нам достаточно последовательно применить операцию XOR ко всем элементам в массиве. Пары одинаковых значений взаимно «уничтожатся», а результатом применения XOR будет само уникальное число.

Реализация #

package single_number

func singleNumber(nums []int) int {
	res := 0

	for _, num := range nums {
		res ^= num
	}

	return res
}

export const singleNumber = (nums: number[]): number => {
    let res = 0

    nums.forEach((num) => {
        res ^= num
    })

    return res
}

Оценка сложности #

n - количество элементов в массиве.

По времени

Сложность по времени O(n), так как мы итерируемся по всем элементам массива.

По памяти

Сложность по памяти O(1), так как мы не создаем дополнительных переменных.

Оригинал задачи на Leetcode

Algorithmics