41.缺失的第一个正数 (Hard)

问题描述

41. 缺失的第一个正数 (Hard)

给你一个未排序的整数数组 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

解题思路

标记

在nums[i]数组上做标记，我们可以将nums数组中的负数都设为n + 1，令num = abs(nums[i])，然后将nums[num - 1]取反，最后遍历修改后的nums[i]，如果都是负数，返回n + 1，否则返回碰到的第一个非负数的索引加一；

置换

如果nums[i] <= nums.size() && nums[i] > 0，那么就将它与nums[num[i] - 1]置换，为了防止死循环，还要判断nums[i] != nums[nums[i] - 1]

代码

标记

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int& num: nums) {
            if (num <= 0) {
                num = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
};
// @lc code=end

置换

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            while (nums[i] > 0 && nums[i] <= nums.size() && nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
                std::swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return nums.size() + 1;
    }
};