题目要求
1
2
3
4
5
6
7
| Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
|
在数组中找到第一个漏掉的正整数。如果可以的话，使用O(N)的时间复杂度和O(1)的空间复杂度。
思路一：暴力排序后寻找
排序后寻找显然是最快的。排序的时间复杂度要依靠java底层的依赖。之后再用O(N)的时间复杂度找到第一个漏掉的整数后即退出遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int firstMissingPositive(int[] nums) {
int size = nums.length;
if(size == 0) return 1;
Arrays.sort(nums);
int positive = 1;
for(int i = 0 ; i<size ; i++){
if(nums[i]<positive) continue;
if(nums[i]>positive) return positive;
positive++;
}
return positive;
}
|
思路二：O(1)空间复杂度
要实现这种空间复杂度，一般需要有限数量的临时变量来记录遍历的有效范围，再利用原有题目中的数据结构来存储其余的临时变量。这些临时变量可以是排除出的量，也可以是有效量。在这里我用leftPointer记录有效数字的开始下标（即将无效数字转移到leftPointer左侧），利用maxPositive记录数组最大有效整数（换句话说，如果一个数组的大小为9，则该数组的最大first missing positive integer即为10，一旦数组中出现重复或是小于1或是大于9的数字，该数字即为无效数字)。当遇到的数字为有效数字时，则将该数字放到对应当前起始下标leftPointer其相应的位置上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public int firstMissingPositive2(int[] nums){
int size = nums.length;
int positive = 1;
int leftPointer = 0;
int maxPositive = size;
while(leftPointer<size){
if(nums[leftPointer] == positive){
leftPointer++;
positive++;
}
else if(nums[leftPointer] > maxPositive || nums[leftPointer] < positive || nums[leftPointer]==nums[leftPointer+nums[leftPointer]-positive]){
leftPointer++;
maxPositive--;
}else{
int temp = nums[leftPointer];
nums[leftPointer] = nums[leftPointer+temp-positive];
nums[leftPointer+temp-positive] = temp;
}
}
return positive;
}
|