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.
A:
就是求和,然后-------哎,可是有重复啊!!!!!!!!
考虑到负值的存在,因此我们需要 设一个值,来记录positive number 的个数。
另外, 记录till now max
Remember, we are required to find the first, i.e. there might exist multiple missing positive integer.
例如: int [] A = {3,3,4,1,1,1};
基本的思路来源于:当设置都封死了我们利用现有算法,也不让用额外的空间, 因此,我们只能更改已给的空间。
哎,这样不行,那样也不行。就只能考虑,在A数组上更改了。
基本思路是: 用地址代表数字内容。 亦即,A[i] 的内容,更改为 i+1.
首先,对于负数。我们统统 set to be zero. 对于正数,改成其相反数。
因此,当遇到一个数字为负值。首先该位置设0, 表明我们 经历过了。
紧接着,就找value 对应的position , 如果该position 已经为正, 则我们现在遇到的这个数字,已经是重复的了。 直接跳过。 如果 A[val -1] < 0。 则继续调整。
经过分析,我们可以看到。虽然for loop 里有while 循环,但是,每个while都至少set 一个A的位置为非负。 因此,总的次数,不超过2*A.length()的。
也就保证了O(n)的效率。
public class Solution { public int firstMissingPositive(int[] nums) { // find a value, called val, put it on position nums[val -1] int n = nums.length; for(int i =0;i< n;i++){ int val = nums[i]; if(val<=0 || val == i+1 || val >= n || nums[val-1] == val) continue; // swap these two position int tmp = nums[i]; nums[i] = nums[val-1]; nums[val-1] = tmp; i--; } for(int i =0;i< n;i++){ if(nums[i] != i+1) return i+1; } return nums.length+1; } }
Mistakes:
1: 没有考虑重复的情况。 例如A = [1, 1].
2: 找到解决方法后, 没有考虑输入为空的情况。 (其实考虑了,但是,直接用assert排除了)
3: 题意理解不透彻, given input A=[1,2], the output is expected to be : 3
Learned:
----------------------------------第二遍------------
思路和上面的不一样:
简单来讲,就是对每一个位置, 如果错位排列的, 把其位置 调整过来。
记得调整的时候,要检查,是否是相同的数字,如果相同,则不必swap了(会有loop)
public class Solution { public int firstMissingPositive(int[] nums) { int n = nums.length; for(int i =0;i<nums.length;i++){ if(nums[i]<=0 || nums[i] >n){ nums[i] = -1; }else if(nums[i] != i+1){ int nextPos = nums[i] - 1; if(nums[i]== nums[nextPos]){ nums[i] = -1; }else{// swap this two position int tmp = nums[i]; nums[i] = nums[nextPos]; nums[nextPos] = tmp; } i--; } } // find the first position that is not a match for(int i =0;i<nums.length;i++) if(nums[i] != i+1) return i+1; return n + 1; } }
No comments:
Post a Comment