缺失的第一个正数
给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1:
输入:nums = [1,2,0]
输出:3
示例 2:
输入:nums = [3,4,-1,1]
输出:2
示例 3:
输入:nums = [7,8,9,11,12]
输出:1
提示:
\(1 <= nums.length <= 5 * 10^5\)
\(-2^{31} <= nums[i] <= 2^{31} - 1\)
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/first-missing-positive
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路1:哈希表
使用哈希表记录出现的数字,并从1开始查找缺失了的最小正整数。
code
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
unordered_map<int,int> cnt;
for(auto item : nums) cnt[item] ++;
int i = 1;
while(1)
{
if(cnt.find(i) == cnt.end()) break;
i ++;
}
return i;
}
};
解题思路2:原地哈希
见注释。
code
class Solution {
public:
//原地算法:使用nums的下标做标记
//i -> i-1的位置,也就是将所有的数摆到该摆的位置
//遍历一遍看看哪里缺失
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for(int i = 0;i < n;i ++)
{
//因为换过来的可能也是1-n之间的数,也需要摆到合适的位置
while(nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] -1])
{
int tmp = nums[i];
nums[i] = nums[tmp-1];
nums[tmp-1] = tmp;
//nums[i]放到了i-1处
//现在的nums[i]是交换后的值,也需要摆到正确位置
}
}
for(int i = 0;i < n;i ++)
{
if(nums[i] != i + 1) return i + 1;
}
return n + 1;
}
};