41. 缺失的第一个正数

[webVueBlog]

41. 缺失的第一个正数

Description

Difficulty: 困难

Related Topics: 数组, 哈希表

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

提示：

• 1 <= nums.length <= 5 * 10⁵
• -2³¹ <= nums[i] <= 2³¹ - 1

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    for (let i = 0; i < nums.length; i++) {
        // 循环nums，当前元素在(0, nums.length)之间，并且nums[nums[i]-1] !== nums[i], 则交换位置
        while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] !== nums[i]) {
            const temp = nums[nums[i] - 1]
            nums[nums[i] - 1] = nums[i]
            nums[i] = temp
        }
    }
    for (let i = 0; i < nums.length; i++) {
        // 循环交换位置之后的数组，判断第一个缺失的正数
        if (nums[i] !== i+1) {
            return i+1
        }
    }
    return nums.length + 1
};