解题思路

本题和“缺失的第一个元素”类似，都可以使用特殊的哈希表来解决，只不过本题没有限定数组内都是正数，且均在n的范围内。

因此本题有3个难点：

  • 负数是不能映射到哈希表的，如何处理负数
  • 数组内元素并不是都在n的范围内的，因此需要解决越界的问题
  • 如何定义哈希函数

针对上述两个问题，有如下解决方案：

  • 负数的问题：对于负数可以直接跳过，统一将负数处理为n + 1，这样就能将负数排除在哈希表的范围
  • 越界问题：对负数统一处理后，就自然可以使用哈希函数来进行映射，找到没被映射的索引，就是第一个缺失的正数

现在处理后的数组元素结构就变成了全部大于等于0的结构，原有负数不会被映射到任何索引，所以可以用模来实现。

对比“缺失的第一个元素”，因为它没有任何限定，直接计算也不会越界，可以使用+n的方法来区分被索引的位置，但是本题有可能越界，所以可以用正负来表示第一个缺失的正数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (auto& num : nums) {
        if (num <= 0) {
            num = n + 1;
        }
    }
    for (int i = 0; i < nums.size(); i++) {
        int num = abs(nums[i]);
        if (num <= n) {
            nums[num - 1] = -abs(nums[num - 1]);
        }
    }
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] > 0) {
            return i + 1;
        }
    }
    return n + 1;
}