跳转至

41 缺失的第一个正数

题目要求\(O(n)\)的时间复杂度和\(O(1)\)的空间复杂度,这意味着:

  • \(O(1)\)的空间复杂度 -> 只能在数组本身操作,不能使用 “把所有元素放入哈希表,再遍历查询”的方法
  • \(O(n)\)的时间复杂度 -> 不能使用“先排序再二分查找“的方法

以下方法名为”原地哈希“,将值为1的元素放到索引0,值为2的元素放到索引1,值为i的元素放到索引i - 1...因此有nums[i] = i + 1

具体做法:

  1. 计算当前元素值对应的索引idx,idx = nums[i] - 1
  2. 找到索引对应的元素nums[idx]
  3. 交换nums[i]和nums[idx]
  4. 交换后,nums[i]为新值,需要继续重复以上做法,直到满足nums[i] == i + 1

当然,要注意以下条件:

  • 本题求的是正整数,因此值为负数的元素可忽略
  • n为数组长度,这意味着:n + 1是一定缺失的(如果某个元素大于等于n + 1,我们最后也会返回n + 1)
    • 如果找不到前n个缺失的正整数,那么缺失的就是n + 1(n为数组长度)
    • 如果某个元素值大于等于n + 1,那么也可以忽略,不用哈希
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; i++){
            while(nums[i] != i + 1){
                // 如果当前数是负数,不需要哈希
                // 如果当前数为 n + 1, 不需要哈希,因为在前面的 n 个元素都找不到的情况下,我们才返回 n + 1
                // 如果当前数和想要交换的数相同,需要跳出循环,否则会死循环
                if(nums[i] <= 0 || nums[i] > n || nums[i] == nums[nums[i] - 1])
                    break;
                // 交换两个数
                int idx = nums[i] - 1;
                nums[i] = nums[idx];
                nums[idx] = idx + 1;
                // 等价于
                // int idx = nums[i] - 1;
                // swap(nums[idx], nums[i]);
            }
        }
        // 遍历一遍数组找到不符合的正整数
        for(int i = 0;i < n;i++){
            if(nums[i] != i + 1)
                return i + 1;
        }
        // 如果没有,则返回n + 1
        return n + 1;
    }
};

\(O(n)\)的时间复杂度

\(O(1)\)的空间复杂度