# 缺失的第一个正数
41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
# 排序
如果不考虑时间问题，只考虑空间问题，这题很好做，将数组排序，用一个 count 记一下最小正数就行
- count 初始为 1
- 对于排序后的数组，遍历，元素记
item item == count ， count 自增item > count 返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int firstMissingPositive(int[] nums) {
Arrays.sort(nums);
int count = 1;
for(int item : nums){
if(item == count){
count++;
}else if(count < item){
return count;
}
}
return count;
}
}
|
# 打表
如果不考虑空间问题，只考虑时间问题，需要用到桶
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int firstMissingPositive(int[] nums) {
int len = nums.length;
int res[] = new int[len+1];
for(int i : nums){
if(i > 0 && i<=len)
res[i] = 1;
}
for(int i = 1 ;i<=len;i++){
if(res[i] == 0){
return i;
}
}
return len+1;
}
}
|
# 原地哈希
时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案就是操作原数组，原地哈希。
对于原数组，将其变为一个 nums[i-1] = i 的形式。
例子：
- 长度为 4 的数组 {4,2,1,3}，原地哈希后 {1,2,3,4}，每个元素满足
nums[i-1] = i 。 - 数组 {4, -1, 1, 3}，原地哈希后 {1, -1, 3, 4}，此时遍历找到第一个满足
nums[i-1] != i 的元素返回对应缺失的正数即可。
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
27
28
| public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
if (i + 1 == nums[i]) {
continue;
}
if (0 < nums[i] && nums[i] <= n && nums[i] != nums[nums[i]-1]) {
swap(nums, i, nums[i] - 1);
i--;
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
public void swap(int[] arr, int i, int j) {
if (i != j) {
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}
}
|
