448. Find All Numbers Disappeared in an Array

Задача

Дан массив nums из n чисел в диапазоне [1, n]. Верните все числа диапазона, которых нет в массиве.

Примеры

Пример 1

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Пример 2

Input: nums = [1,1]
Output: [2]

Решение

Решение

/**
 * Сложность по времени: O(n)
 * - Создание Set занимает O(n).
 * - Цикл проверки от 1 до n занимает O(n).
 *
 * Сложность по памяти: O(n)
 * - Мы храним все уникальные числа массива в Set. Это линейная память.
 */
var findDisappearedNumbers = function(nums) {
    const numSet = new Set(nums);
    const result = [];
 
    for (let i = 1; i <= nums.length; i++) {
        if (!numSet.has(i)) {
            result.push(i);
        }
    }
 
    return result;
};

Решение 2 (Cyclic Sort)

/**
 * Сложность по времени: O(n)
 * - Каждое число встает на своё место или отбрасывается за O(1) операций (swap).
 * - Суммарно цикл while выполнится не более N раз за всю программу.
 *
 * Сложность по памяти: O(1)
 * - Модифицируем исходный массив, меняя элементы местами.
 */
var findDisappearedNumbers = function(nums) {
    let i = 0;
    while (i < nums.length) {
        // Правильная позиция для числа nums[i]
        const correctIndex = nums[i] - 1;
 
        // Если число стоит не на своем месте И на том месте не стоит уже такое же число
        if (nums[i] !== nums[correctIndex]) {
            // Swap (меняем местами)
            [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
        } else {
            i++;
        }
    }
 
    // Теперь ищем индексы, где стоят "неправильные" числа
    const result = [];
    for (let j = 0; j < nums.length; j++) {
        if (nums[j] !== j + 1) {
            result.push(j + 1);
        }
    }
 
    return result;
};