41 缺失的第一个正数
题目要求\(O(n)\)的时间复杂度和\(O(1)\)的空间复杂度,这意味着:
- \(O(1)\)的空间复杂度 -> 只能在数组本身操作,不能使用 “把所有元素放入哈希表,再遍历查询”的方法
- \(O(n)\)的时间复杂度 -> 不能使用“先排序再二分查找“的方法
以下方法名为”原地哈希“,将值为1的元素放到索引0,值为2的元素放到索引1,值为i的元素放到索引i - 1...因此有nums[i] = i + 1
具体做法:
- 计算当前元素值对应的索引idx,idx = nums[i] - 1
- 找到索引对应的元素nums[idx]
- 交换nums[i]和nums[idx]
- 交换后,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)\)的空间复杂度