少则得，多则惑

题目描述

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

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

示例 1：

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

输出：3

解释：范围 [1,2] 中的数字都在数组中。

示例 2：

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

输出：2

解释：1 在数组中，但 2 没有。

示例 3：

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

输出：1

解释：最小的正数 1 没有出现。

提示：

1 <= nums.length <= 105

-231 <= nums[i] <= 231 - 1

思路分析

• 原地哈希

• 核心思想：将元素nums[i]尽可能地放到下标i上面

完整代码

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

代码解释

1. 初始化变量：

    int n = nums.size();

• n 记录数组 nums 的大小。

2. 第一次遍历：原地哈希：

    for(int i = 0; i < n; i++)
        while(nums[i] >= 0 && nums[i] < n && nums[nums[i]] != nums[i])
            swap(nums[i], nums[nums[i]]);

• 这个循环的作用是将数组中的每个元素尽可能地放置在它应该在的位置上。

• while 循环的条件是：

• nums[i] >= 0：元素值必须是非负数（正整数）。

• nums[i] < n：元素值必须小于数组的大小 n，因为数组的索引是从 0 到 n-1。 - nums[nums[i]] != nums[i]：元素值 nums[i] 应该放置在索引 nums[i] 处，但当前位置不是它。

• swap(nums[i], nums[nums[i]])：将元素 nums[i] 交换到它应该在的位置 nums[nums[i]]。

  举个例子：

  • 如果 nums[i] 是 1，那么它应该被放置在索引 1 处。如果 nums[i] 是 2，那么它应该被放置在索引 2 处。
  • 这个过程会一直进行，直到 nums[i] 无法再交换为止。

3. 第二次遍历：寻找第一个缺失的正整数：

    for(int i = 1; i < n; i++)
        if(nums[i] != i)
            return i;

• 从索引 1 开始遍历数组，检查每个位置 i 的值是否等于 i。

• 如果 nums[i] != i，说明索引 i 处没有放置正确的值，即 i 是第一个缺失的正整数，返回 i。

4. 处理边界情况：

    return nums[0] == n ? n + 1 : n;

• 如果数组中所有的正整数都按顺序放置在正确的位置上，那么第一个缺失的正整数应该是 n。

• 但我们需要检查 nums[0] 是否等于 n：

• 如果 nums[0] == n，说明数组中包含 n，那么第一个缺失的正整数应该是 n+1。

• 否则，第一个缺失的正整数是 n。

1. 原地哈希：

• 这个算法的核心思想是，将数组中的每个正整数放到它应该在的位置上。比如，数字 1 应该放在索引 1 处，数字 2 应该放在索引 2 处，依此类推。如果某个位置上的数字不是它应该在的位置，就把它放到正确的位置上。

2. 寻找缺失的正整数：

• 经过上面的原地哈希操作后，数组中的每个正整数都应该在它应该在的位置上。如果某个位置上的数字不是它应该在的位置，那么这个位置的索引就是第一个缺失的正整数。

3. 处理特殊情况：

• 如果数组中的所有正整数都按顺序放置在正确的位置上，那么第一个缺失的正整数应该是数组的大小 n 或 n+1，具体取决于 nums[0] 的值。