41-First Missing Positive

【题目】

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.

【analyze】

1.由于是无序的，所以处理起来有点麻烦。可以考虑将正确的正数放在正确的索引位置上，然后再遍历整个数组

2.有两个地方一直没注意到：一.当前位置交换后，还需要判断；二.若解决第一个问题后（加入while），当前值与交换的值相同时会进入死循环

【算法】

v1:比较无耻的做法，先排序
public class Solution {public int firstMissingPositive(int[] nums) {Arrays.sort(nums);int flag=1;int i=0;while(i<nums.length) {if(nums[i]>0) {if(nums[i]==flag) {flag++;i++;while(i<nums.length&&nums[i]==nums[i-1])i++;}elsereturn flag;}else i++;}return flag;}
}v2:
public class Solution {public int firstMissingPositive(int[] nums) {if(nums==null||nums.length<1)return 1;int len=nums.length;for(int i=0;i<nums.length;i++) {while(nums[i]!=i+1&&nums[i]>0&&nums[i]<=len) {if(nums[i]==nums[nums[i]-1])break;int temp=nums[i];nums[i]=nums[temp-1];nums[temp-1]=temp;}}for(int i=0;i<len;i++) {if(nums[i]!=i+1)return i+1;}return len+1;}
}