41. 缺失的第一个正数

41. 缺失的第一个正数

方法：原地哈希

解题思路

• 原地哈希：在原来的数组基础上构建哈希表，不占用额外的空间
• 在本题中，设数组大小为 \(n\)；
  • 若从 \([1, n]\) 都出现了，则返回 \(n + 1\)；
  • 若 \([1, n]\) 中有数没有出现，则在 \([1, n]\) 之间；
  • 故答案范围在 \([1, n + 1]\) 之间。
• 对于数组中 \(nums[i] <= 0\) 的元素为干扰项将其设置为 \(n + 1\) （或者大于 \(n\) 的任何数），说明该元素对答案没有影响；
• 接着原地构建哈希表，\(x = abs(nums[i])\)，若 \(x <= n\)，表明该元素出现过，则另 \(nums[x - 1] = -abs(nums[x - 1])\)，打上负号标记，说明当前索引的值存在；
• 然后遍历哈希表，若有第一个 \(nums[i] > 0\)，表明正整数 \(i + 1\) 未出现且为最小，否则返回 \(n + 1\)。

代码

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

复杂度分析

时间复杂度：\(O(n)\)；
空间复杂度：\(O(1)\)。