给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
进阶:你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗?
示例 1:
输入:nums = [1,2,0]
输出:3
示例 2:
输入:nums = [3,4,-1,1]
输出:2
示例 3:
输入:nums = [7,8,9,11,12]
输出:1
提示:
0 <= nums.length <= 300
-2^31 <= nums[i] <= 2^31 - 1
令数组长度为 n
,那么答案必然在 [1, n + 1]
范围内。
因此我们可以使用「桶排序」的思路,将每个数放在其应该出现的位置上。
基本思路为:
nums[0]
的位置上,2 出现在 nums[1]
的位置上,…,n
出现在 nums[n - 1]
的位置上。不在 [1, n]
范围内的数不用动。例如样例中 [3,4,-1,1]
将会被预处理成 [1,-1,3,4]
。
nums
,找到第一个不在应在位置上的 [1, n]
的数。如果没有找到,说明数据连续,答案为 n + 1
例如样例预处理后的数组 [1,-1,3,4]
中第一个 nums[i] != i + 1
的是数字 2(i = 1)。
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
while (nums[i] >= 1 && nums[i] <= n && nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
swap(nums, i, nums[i] - 1);
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) return i + 1;
}
return n + 1;
}
void swap(int[] nums, int a, int b) {
int c = nums[a];
nums[a] = nums[b];
nums[b] = c;
}
}
还记得最早我在 【刷穿 LeetCode】4. 寻找两个正序数组的中位数 跟你说过,对于一些从文字上限制我们的题目,我们应该如何分析能否采用别的做法来 AC。
这对于比赛和机试,这种要求我们尽快 AC 的场景来说,尤为重要。
总的来说,你可以根据直观解法的时空复杂度、文字限制的时空复杂度和数据范围等几个方面来判断。
对于本题而言,我们可以很容易想到先排序,再遍历的做法:
排序的复杂度为
;找答案的过程需要枚举 [1, n]
,然后通过「二分」找当前的枚举值是否在排序数据中,复杂度为
。因此整体复杂度为
。
而文字要求我们使用
复杂度的解法。这时候我们基本上可以不看数据范围就可以确定
能做。
因为
和
并没有差多少,哪怕数据范围出到极限
。
= 23,数值非常小,
可以等效看做一个常数计算为 23 的
解法。没有一个支持多语言的 OJ 卡常可以做到
超时,而
能过。何况本题的数据范围只有 300,可以说怎么做都行。
PS. 复杂度分析本身就是渐进分析,23 作为常数可以说一点都不大,大家不要被直觉骗了。
解法代码:
class Solution {
public int firstMissingPositive(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
for (int i = 1; i <= n; i++) {
if (Arrays.binarySearch(nums, i) < 0) return i;
}
return n + 1;
}
}
你会发现,在 LeetCode 上
解法和
解法的执行用时没有差别。
这是我们「刷穿 LeetCode」系列文章的第 No.41
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加,为了方便我们统计进度,我们将按照系列起始时的总题数作为分母,完成的题目作为分子,进行进度计算。当前进度为 41/1916
。
为了方便各位同学能够电脑上进行调试和提交代码,我在 Github 建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。