Given an unsorted integer array, find the first missing positive integer.
For example,
Given
and
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.
Solution 1: if the nums are 1,2,...n. We put it in final position. Then iterate the array again. 1st number not in position is the missing one.
public 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[i]!=nums[nums[i]-1])
swap(nums,i,nums[i]-1);
for (int i=0; i<n; i++)
if (nums[i]!=i+1) return i+1;
return n+1;
}
private void swap(int[] nums, int i, int j) {
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
没有评论:
发表评论