41. 缺失的第一个正数
给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。
示例 1:
1 | 输入: [1,2,0] |
示例 2:
1 | 输入: [3,4,-1,1] |
示例 3:
1 | 输入: [7,8,9,11,12] |
提示:
你的算法的时间复杂度应为O(n),并且只能使用常数级别的额外空间。
如果没有时空复杂度要求可以很容易实现:
- 将数组所有数放入哈希表,从 1 开始枚举正整数,并判断其是否在哈希表中。
- 将从 1 开始枚举正整数,遍历数组判断其是否存在。
第一种方法时间复杂度O(n),空间复杂度O(n);第二种方法时间复杂度O(n^2),空间复杂度O(1)。
此题要求时间复杂度O(n),空间复杂度O(1)。如果题目给的数组是不可修改的,那么不存在满足要求的算法,如果我们可以修改给定的数组,那么可以做到满足要求的算法。
方法一:哈希表
我们可以将给定数组当作哈希表。对于一个长度为 N 的数组来说,没有出现的最小正整数只能在[1, N + 1] 中出现。如果[1, N]都出现,那么答案为 N + 1,否则答案是 [1, N] 中没有出现的最小正整数。这样一来,我们将所有在 [1, N] 中的数放入哈希表,正好数组的长度为 N ,我们可以将其设计为哈希表:
1 | 遍历数组,对于遍历到的数 x ,如果 x ∈ [1, N],将数组中第 x - 1 个位置(下标从 0 开始)上的数变为负数。在遍历结束后,如果所有位置都为负数,那么答案是 N + 1,否则答案是正数的位置加 1 。 |
对于数组中的负数我们首先将其变为 N + 1 ,然后遍历数组将[1, N] 中出现的数字对应的位置上的数字变为负数,再次遍历数组,数组中数字为正数的位置加 1 即为结果,全为负数则结果为 N + 1。
1 | class Solution { |
时间复杂度O(n),空间复杂度O(1)。
方法二:置换
与方法一类似,将数组当作哈希表,我们将下标为x - 1
的位置放数字 x
。我们对数组进行一次遍历,如果遍历到的数字 x = nums[i] 且 x ∈ [1, N] ,我们直到 x 应该放置在 x - 1 位置上,那么我们交换 nums[i] 和 nums[x - 1],这样 x 就出现在了正确的位置,注意当 nums[i] == nums[x - 1] 时应该直接进行下次遍历,不再交换。
1 | class Solution { |
时间复杂度O(n),最多进行 n 次交换。空间复杂度O(1)。
v1.5.2