常见思想

1.数组原地替换---把数字i放在数组索引i的位置,比如0放在arr[0]的位置，1放在arr[1]的位置☆☆☆☆☆

 题目1.无序数组包含正数，负数和0，计算数组中从0开始缺失的自然数，要求时间复杂度O(n),空间复杂度O(1)

      比如：[1,2,3,-6.0] 输出:4   [-3,1,2,3,8]  输出:0

代码如下

//无序数组 正数 负数  0
    //寻找从0开始缺失的自然数
    //[-3,2,3,5]  0
    //[-3,0,3,5]  1
    //[-3,3,0,5]  1
    //时间复杂度O(n) 空间复杂度O(1)
    public static void main(String[] args) {
//        int[] arr= new int[]{-3, 3, 0, 5};
//        int[] arr= new int[]{-3, 3, 0,1, 5};
        int[] arr= new int[]{-3, 2, 0,1,4, 5};
        int num = GetLossNum2(arr);
        System.out.println("num:"+num);

    }

    //时间复杂度O(n),空间复杂度O(n)
    public static int GetLossNum(int[] arr){
        int[] res=new int[arr.length];
        for(int i=0;i<arr.length;i++){
            if(arr[i]<0 ||arr[i]>=arr.length){
                continue;
            }
            res[arr[i]]=1;
        }
        for(int i=0;i<res.length;i++){
            if(res[i]==0){
                return i;
            }
        }
        return 0;
    }

    //-3, 3, 0,2, 5
    //时间复杂度O(n),空间复杂度O(1)
    public static int GetLossNum2(int[] arr) {
        int temp;
        for (int i = 0; i < arr.length; i++) {
            while (arr[i] >= 0 && arr[i] < arr.length && arr[i] != i) {
                temp = arr[arr[i]];
                arr[arr[i]] = arr[i];
                arr[i] = temp;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != i) {
                return i;
            }
        }
        return 0;
    }

题目2.打印重复的数，时间复杂度O(n),空间度复杂度O(1) 

比如数组[1,2,3,4,2,3]  输出:2或者3

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/----题目地址

代码如下

//无序数组 正数 负数  0
    //寻找从0开始缺失的自然数
    //[-3,2,3,5]  0
    //[-3,0,3,5]  1
    //[-3,3,0,5]  1
    //时间复杂度O(n) 空间复杂度O(1)
    public static void main(String[] args) {
//        int[] arr= new int[]{-3, 3, 0, 5};
//        int[] arr= new int[]{-3, 3, 0,1, 5};
        int[] arr= new int[]{-3, 2, 0,1,4, 5};
        int num = GetLossNum2(arr);
        System.out.println("num:"+num);

    }

    //时间复杂度O(n),空间复杂度O(n)
    public static int GetLossNum(int[] arr){
        int[] res=new int[arr.length];
        for(int i=0;i<arr.length;i++){
            if(arr[i]<0 ||arr[i]>=arr.length){
                continue;
            }
            res[arr[i]]=1;
        }
        for(int i=0;i<res.length;i++){
            if(res[i]==0){
                return i;
            }
        }
        return 0;
    }

    //-3, 3, 0,2, 5
    //时间复杂度O(n),空间复杂度O(1)
    public static int GetLossNum2(int[] arr) {
        int temp;
        for (int i = 0; i < arr.length; i++) {
            while (arr[i] >= 0 && arr[i] < arr.length && arr[i] != i) {
                temp = arr[arr[i]];
                arr[arr[i]] = arr[i];
                arr[i] = temp;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != i) {
                return i;
            }
        }
        return 0;
    }