缺失的第一个正数
# 📃 题目描述
题目链接:41. 缺失的第一个正数 (opens new window)
# 🔔 解题思路
可以马上想到用 HashMap 存 nums,然后从整数 1 开始遍历,第一个在 Map 中找不到的数就是第一个缺失的正整数,但是这种做法的空间复杂度是 O(N)
想要空间复杂度 O(1),可以用数组来代替哈希表
即下标为 i 存储整数 i + 1(之所以不用下标 i 存储整数 i,是因为这道题目显然不需要 0 这个数)
- 由于题目要求我们「只能使用常数级别的空间」,而要找的数一定在 [1, N + 1] 左闭右闭(这里 N 是数组的长度)这个区间里。因此,我们可以就把原始的数组当做哈希表来使用。事实上,哈希表其实本身也是一个数组;
- 我们要找的数就在 [1, N + 1] 里,最后 N + 1 这个元素我们不用找。因为在前面的 N 个元素都找不到的情况下,我们才返回 N + 1;
- 那么,我们可以采取这样的思路:就把 1 这个数放到下标为 0 的位置, 2 这个数放到下标为 1 的位置,按照这种思路整理一遍数组。然后我们再遍历一次数组,第 1 个遇到的它的值不等于下标的那个数,就是我们要找的缺失的第一个正数。
class Solution {
public int firstMissingPositive(int[] nums) {
// corner case
if (nums == null || nums.length == 0) {
return 1;
}
int i = 0;
while (i < nums.length) {
// nums 作为哈希表只能存储 [1, nums.length] 的数
if (nums[i] <= 0 || nums[i] == i + 1 || nums[i] > nums.length) {
i ++;
continue;
}
// nums[i] >= 0 && nums[i] != i + 1 && nums[i] <= nums.length
int index = nums[i] - 1;
// nums[i] 和 nums[index] 交换
if (nums[index] != nums[i]) {
swap(nums, i, index);
}
// 如果 nums[i] 已经等于 nums[index] 了,说明存在重复数(比如 [1, 1]),直接 i ++ 就行
// 不 i++ 的话会陷入死循环
else {
i ++;
}
}
for (int j = 0; j < nums.length; j ++) {
if (nums[j] != j + 1) {
return j + 1;
}
}
// 前面的 N 个元素都找不到的情况下,返回 N + 1
return nums.length + 1;
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10