NC30：缺失的第一个正数

题目：缺失的第一个正数

思路1：计数排序：对0,1,2,...,n范围内的数把他放到对应的下标处。比如对于元素i放到下标i-1处，然后对数组从前往后遍历，找到第一个不匹配的，即是最小缺失正数。

public class Solution {
    public int firstMissingPositive(int[] A) {
        if(A==null || A.length==0){
            return 1;
        }
        int n=A.length;
        for(int i=0;i<n;i++){
            //A[i] - 1 < A.length 超出范围不交换
            //A[i] != A[A[i] - 1] 相等不交换
            while(A[i]>0 && A[i]!=i+1 && A[i]<=n && A[i]!=A[A[i]-1]){
                swap(A,i,A[i]-1);
            }
        }
        for(int i=0;i<n;i++){
            if(A[i]!=i+1){
                return i+1;
            }
        }
        return A[n-1]+1;
    }

    public void swap(int[] A,int i,int j){
        int tmp=A[i];
        A[i]=A[j];
        A[j]=tmp;
    }
}

思路2：返回得数最大不会超过数组长度加一，依次遍历。

public class Solution {
    public int firstMissingPositive(int[] A) {
        int n=A.length;
        for(int i=1;i<=n;i++)
        {
            int count=0;
            for(int j=0;j<n;j++)
            {
                if(A[j]==i)
                    count=1;
            }
                if(count==0)
                    return i;
        }
        return n+1;
    }
}

思路3：先将数组排序,当排序后的数组的最后一个元素为负或为0即缺失的为1,定义一个目标min先定义为1,遍历数组,在遍历过程中将数组值与目标值比较是否相等,即min从最小正整数1开始增长

    public int minNumberdisappered (int[] arr) {
        // write code here
        int len=arr.length;
        Arrays.sort(arr);
        if(len==0 || arr[len-1] <=0){
            return 1;
        }
        int min=1;
        for(int i=0;i<len;i++){
            if(arr[i]==min){
                min++;
            }
        }
        return min;
    }

思路4：

1. 统计出数组中的正数个数，k个
2. 缺失的正整数或者是k+1，或者在1-k之间
3. 要做的事情就是对于1-k之间的数字，放到它该去的位置，这个过程一定说O(n)内完成的
4. 1-k之间的数都去了它对应的位置，然后遍历，第一个不应该出现的数字就是，如果0-k-1的数字都符合，那就是k+1

    public static int missNum(int[] arr,int n){
        if(arr.length<2 || arr==null){
            return -1;
        }
        int[] help=new int[n];
        for(int i=0;i<n;i++){
            if(arr[i]>0 && arr[i]<=n){
                help[arr[i]-1]=arr[i];
            }
        }
        int temp=1;
        for(int i=0;i<n;i++){
            if(temp!=help[i]){
                break;
            }
            else{
                temp++;
            }
        }
        return temp;
    }

左神：

private static int findnum(int a[]) { 
   int l=0;//l表示已经从1到L已经出现（左边界），l的初值为0。
   int r=a.length;//如果一个数字过大（不合法）扔掉，用r表示这个右边界，r初始值长度
         while(l<r){
                    if(a[l]==l+1){//a[0]=1,0-k内合法的数有多少
                        l++;
                    }else if(a[l]<=l||a[l]>r||a[l]==a[a[l]-1]){//不合法,
                                            //a[1]=3 a[a[1]-1]=a[2]
                        a[l] = a[--r];//缩短右边界
                    }else{//合法但是没有在理想的位置上
                        swap(a,l,a[l]-1);//交换新数l和已排好的a[l]-1
                    }
                }                                    
    return l+1;//返回a[l]=l+1,0-l为已出现的数，l+1代表未出现的数
}
private static void swap(int[] arr, int a,int b){
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}