41.缺失的第一个正数

缺失的第一个正数

给你一个未排序的整数数组 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^5\)
\(-2^{31} <= nums[i] <= 2^{31} - 1\)

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/first-missing-positive
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路1：哈希表

使用哈希表记录出现的数字，并从1开始查找缺失了的最小正整数。

code

class Solution {
public:

    int firstMissingPositive(vector<int>& nums) {
        
        unordered_map<int,int> cnt;

        for(auto item : nums) cnt[item] ++;

        int i = 1;
        while(1)
        {
            if(cnt.find(i) == cnt.end()) break;
            i ++;
        }

        return i;

    }
};

解题思路2：原地哈希

见注释。

code

class Solution {
public:
    //原地算法：使用nums的下标做标记
    //i -> i-1的位置,也就是将所有的数摆到该摆的位置
    //遍历一遍看看哪里缺失

    int firstMissingPositive(vector<int>& nums) {
        
        int n = nums.size();

        for(int i = 0;i < n;i ++)
        {
            //因为换过来的可能也是1-n之间的数，也需要摆到合适的位置
            while(nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] -1])
            {
                int tmp = nums[i];
                nums[i] = nums[tmp-1];
                nums[tmp-1] = tmp;
                //nums[i]放到了i-1处
                //现在的nums[i]是交换后的值，也需要摆到正确位置
            }
        }

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

        return n + 1;

    }
};