41. First Missing Positive

    /*
     * 41. First Missing Positive 
     * 2016-5-4 by Mingyang
     * 这道题目要求线性时间和constant空间，本来我想多用一个数组，把对应的数字直接填满另外的数组
     * ，但是如果只能有一个array的话，就是另外一个情况呢
     * 需要考虑那个地方是否有值了 A[0]=1,A[1]=2,A[2]=3...如果抽到了3，就把A2换成3
     * ，不过一定要i--，因为只有减了以后再判断是不是漏掉一个什么的
     * 首先是我自己的代码，写的确实比较丑，因为自己是A[0]=0,A[1]=1的思路，殊不知稍稍变通一下就可以世界变的更加美好
     */
    public int firstMissingPositive1(int[] nums) {
        int len=nums.length;
        if(nums==null||len==0)
          return 1;
       if(len==1)
         return nums[0]==1?2:1;
        for(int i=0;i<len;i++){
            if(nums[i]<0||nums[i]>len-1||nums[i]==nums[nums[i]])
              continue;
            else{
             swap2(nums,i,nums[i]);
             i--;
            }
        }
        for(int i=0;i<len;i++){
            if(nums[i]!=i&&i!=0){
                return i;
            }
        }
        if(nums[0]!=0&&nums[0]==nums[len-1]+1){
           return nums[0]+1; 
        }
        return len;
    }
    public void swap2(int[] array, int j,int k){
        int temp=array[j];
        array[j]=array[k];
        array[k]=temp;
    }
    //稍稍错位一下能让代码更加简单
    public int firstMissingPositive(int[] A) {
        if (A == null || A.length == 0)
            return 1;
        for (int i = 0; i < A.length; i++) {
            if (A[i] <= A.length && A[i] > 0 && A[A[i] - 1] != A[i]) {
                int temp = A[A[i] - 1];
                A[A[i] - 1] = A[i];
                A[i] = temp;
                i--;
            }
        }
        for (int i = 0; i < A.length; i++) {
            if (A[i] != i + 1)
                return i + 1;
        }
        return A.length + 1;
    }