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

Привет, друзья!

Новогодние праздники прошли и пришла пора возвращаться к задачам. Я понимаю, что эта рабочая почти неделя многим далась тяжело, поэтому мы начнем с простой задачи, но на ту тему, которую еще не разбирали. Будет интересно!

Сложность: 🟢 Легкая

ℹ️ Описание

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

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

⚠️ Ограничения

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

1️⃣ Пример

Входящие данные

[2, 2, 1]

Ответ

1

2️⃣ Пример

Входящие данные

[4, 1, 2, 1, 2]

Ответ

4

✅ Решение

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

В результате мы получим такое решиние.

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.

Посмотреть разбор решения в блоге

#array #easy #bit_manipulation