缺失的第一个正数

缺失的第一个正数

对于一个长度为 N 的数组，其中没有出现的最小正整数只能在[1,N+1]中。这是因为如果[1,N]都出现了，那么答案是N+1，否则答案是[1,N]中没有出现的最小正整数。

这样一来，我们将所有在[1,N]范围内的数放入哈希表，也可以得到最终的答案。而给定的数组恰好长度为N。

这让我们有了一种将数组设计成哈希表的思路：我们对数组进行遍历，对于遍历到的数x，如果它在[1,N]的范围内，那么就将数组中的第x−1个位置（注意：数组下标从0开始）打上「标记」。在遍历结束之后，如果所有的位置都被打上了标记，那么答案是N+1，否则答案是最小的没有打上标记的位置加1。

那么如何设计这个「标记」呢？由于数组中的数没有任何限制，因此这并不是一件容易的事情。但我们可以继续利用上面的提到的性质：由于我们只在意[1,N]中的数，因此我们可以先对数组进行遍历，把不在[1,N]范围内的数修改成任意一个大于N的数（例如 N+1）。这样一来，数组中的所有数就都是正数了，因此我们就可以将「标记」表示为「负号」。

算法的流程如下：

• 我们将数组中所有小于等于0的数修改为N+1;

• 我们遍历数组中的每一个数x，它可能已经被打了标记，因此原本对应的数为∣x∣。如果∣x∣∈[1,N]，那么我们给数组中的第∣x∣−1个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加；

• 在遍历完成之后，如果数组中的每一个数都是负数，那么答案是N+1，否则答案是第一个正数的位置加1。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(auto& 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;
    }
};