缺失的第一个正数

问题

缺失的第一个正数 原题链接：https://leetcode.cn/problems/first-missing-positive

解法

首先就是个人的做法，很容易想到借助hash表来转化存在的数字。然后借助数字自增来快速判断最小缺失的正整数。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_map<int,bool> mp;
        for(auto& item:nums){
            if(!mp.count(item)){
                mp[item]=true;
            }
        }

        int ans=1;
        while(true){
            if(!mp.count(ans)) return ans;
            ans++;
        }
    }
};

第二种方法要运用抽屉原理来合理的节省寻找花费：
1.范围收缩（抽屉原理）:长度为 n 的数组里，最小缺失正整数一定落在 [1, n+1]。
1.1如果 1..n 都在，那答案就是 n+1；
1.2否则就是其中某个缺失的数。
→ 所以我们只需关注 1..n 这些“有用数”，其他（≤0 或 >n）都可以视为“垃圾”。

2.用数组当哈希桶（原地哈希 / 置换）:把每个在 [1..n] 范围内的数 x 放到“它的家”——下标 x-1 的位置：
2.1想让 nums[x-1] == x；
2.2通过不断交换把数放回家；
2.3处理过程中忽略 ≤0、>n、以及 重复 的数（避免死循环）。

3.最终一遍扫描：第一个不在家（nums[i] != i+1）的位置 i，答案就是 i+1；若都在家，答案是 n+1。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        const int n=nums.size();
        //转换到对应位置
        for(int i=0;i<n;i++){
            while(nums[i]>=1 && nums[i]<=n){//之所以要循环，因为被换的那个可能没到最终位置
                int to=nums[i]-1;
                if(nums[to]==nums[i]) break;//已经在家/重复出现
                swap(nums[to],nums[i]);
            }
        }
        //第一个不符合的，或者都符合就是n+1（抽屉原理）；
        for(int i=0;i<n;i++){
            if(nums[i]!=i+1) return i+1;
        }
        return n+1;
    }
};