@NewWorld
2016-09-24T23:07:34.000000Z
字数 862
阅读 1107
LeetCode
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.
分析题干,已知数组大小为 n,而最小的 n 个正数是 1~n,那么存在两种情况:
1. 数组中正好包含了 1~n 这 n 个数,此时缺失的最小正数为 n+1;
2. 数组中包含了 1~n 这个范围外的数,那么缺失的最小正数必然是在 1~n 这个范围里。
如此,我们只需要关注 1~n 这 n 个数是否出现就行。使用查找表的思想,得到一个空间复杂度O(n),时间复杂度O(n)的算法,实现代码如下:
public class Solution {
public int firstMissingPositive(int[] nums) {
if (nums == null || nums.length == 0) {
return 1;
}
// 创建一个查找表,用来记录 1~nums.length 中数字出现的情况
boolean[] exist = new boolean[nums.length];
for (int i=0; i<nums.length; i++) {
if (nums[i] <= nums.length && nums[i] > 0) {
exist[nums[i]-1] = true;
}
}
// 数组中缺失了 1~nums.length 范围内的数
for (int i=0; i<nums.length; i++) {
if (!exist[i]) {
return i+1;
}
}
// 数组中包含了 1~nums.length
return nums.length+1;
}
}
当然也可以直接在原数组上进行操作,将数转移到对应的位置上,得到一个空间复杂度O(1)的算法,具体实现并不复杂,众位看官可以动手试试。