echo

任生命穿梭 时间的角落

0%

缺失的第一个正数

41. 缺失的第一个正数

给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。

示例 1:

1
2
输入: [1,2,0]
输出: 3

示例 2:

1
2
输入: [3,4,-1,1]
输出: 2

示例 3:

1
2
输入: [7,8,9,11,12]
输出: 1

提示:

你的算法的时间复杂度应为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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
//将所有负数变为 n + 1
for(int i = 0; i < n; i++){
if(nums[i] <= 0){
nums[i] = n + 1;
}
}
//上标记
for(int i = 0; i < n; i++){
//数组中数字可以为负数,应对其取绝对值
int x = Math.abs(nums[i]);
if(x < n + 1){
nums[x - 1] = -Math.abs(nums[x - 1]);
}
}
//再次遍历数组,得到答案
for(int i = 0; i < n; i++){
if(nums[i] > 0){
return i + 1;
}
}
return n + 1;
}
}

时间复杂度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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for(int i = 0; i < n; i++){
while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]){
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}

for(int i = 0; i < n; i++){
if(nums[i] != i + 1){
return i + 1;
}
}
return n + 1;
}
}

时间复杂度O(n),最多进行 n 次交换。空间复杂度O(1)。

Powered By Valine
v1.5.2