41. 缺失的第一个正数

题目链接：https://leetcode.cn/problems/first-missing-positive/

代码

/**
 * 41. 缺失的第一个正数
 * https://leetcode.cn/problems/first-missing-positive/
 */

// 正数 排序 去重 遍历
function firstMissingPositive(nums: number[]): number {
    nums = nums.filter(item => item > 0).sort((a, b) => a - b);
    nums = Array.from(new Set(nums));
    let a = 0;
    const len = nums.length;
    for (let i = 0; i < len; i++) {
        if (nums[i] !== a + 1) {
            return a + 1;
        }
        a++;
    }
    return a + 1;
}

// 根据索引换位置
function firstMissingPositive2(nums: number[]): number {
    const len = nums.length;
    for (let i = 0; i < len; i++) {
        // 保证在[1,len]，保证不重复
        while (1 <= nums[i] && nums[i] <= len && nums[i] !== nums[nums[i] - 1]) {
            const j = nums[i] - 1;
            [nums[i], nums[j]] = [nums[j], nums[i]];
        }
    }

    for (let i = 0; i < len; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }

    return len + 1;
}

思路

方法一：排序 + 去重 + 遍历

先过滤出正数，排序去重后，遍历查找第一个缺失的正数。

• 时间复杂度 $O(n\log n)$，主要是排序的复杂度
• 空间复杂度 $O(n)$，需要额外的数组空间

方法二：根据索引换位置（推荐）

利用数组索引作为哈希表，将数字 i 放到索引 i - 1 的位置上。遍历数组，如果 nums[i] 在 [1, len] 范围内且不在正确位置上，就交换到正确位置。最后遍历数组，第一个位置不匹配的就是缺失的第一个正数。

• 时间复杂度 $O(n)$，每个元素最多被交换一次
• 空间复杂度 $O(1)$