查找整数数组中缺失的数字

数组arr大小为n，取值范围0~n-1，如果数组有重复数字，则某些数字就会缺失，试着找出缺失数字。

思路：如果数组arr没有缺失数字，则含有n个数字的数字的数字正好覆盖0~n-1，如果某个数字重复出现，则必然有缺失的数字。可以新建一个大小为n的辅助数组copyArr，无需对原数组排序，直接遍历原数组，把下标i对应的数字arr[i]存入新数组的对应下标中。然后，遍历辅助数组，如果下标i与copyArr[i]不相等，则说明i缺失了。

public class FindAllMissNumber {

    public ArrayList<Integer> getMissNumber(int[] numbers) {

        ArrayList<Integer> arrayList = new ArrayList<>();

        if(numbers == null || numbers.length < 0){

            return arrayList;

        }

        int[] copyArr = new int[numbers.length];

        for(int i = 0; i < numbers.length; i++) {

            copyArr[numbers[i]] = numbers[i];

        }

        for(int i = 0; i < numbers.length; i++){

            if(copyArr[i] != i) {

                arrayList.add(i);

            }

        }

        return arrayList;

    }

    private static void printResult(int[] arr){

        FindAllMissNumber findAllMissNumber = new FindAllMissNumber();

        ArrayList<Integer> arrayList = findAllMissNumber.getMissNumber(arr);

        if(arrayList.size() == 0){

            System.out.println("No miss number");

        } else {

            System.out.println(arrayList.toString());

        }

    }

    public static void main(String[] args){

        //null

        int[] arr1 = null;

        printResult(arr1);

        //无重复

        int[] arr2 = {0,1,2,3,4,5,6};

        printResult(arr2);

        //有1个重复数字

        int[] arr3 = {0,1,2,3,4,2,6};

        printResult(arr3);

        //有多个重复数字

        int[] arr4 = {0,1,2,3,4,2,6,4};

        printResult(arr4);

    }

}

---------------------

作者：翁正存

来源：CSDN

原文：https://blog.csdn.net/Wengzhengcun/article/details/86358887

版权声明：本文为博主原创文章，转载请附上博文链接！