01_数组中重复的数字

要求：

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

思路：

方法一：数组的长度为 n 且所有数字都在 0 到 n-1 的范围内，我们可以将每次遇到的数进行"归位"，当某个数发现自己的"位置"被相同的数占了，则出现重复。
方法二:哈希表
方法三：排序

    // 方法一
    public boolean duplicate(int[] numbers, int length, int[] duplication) {
        // 判断边界
        if (numbers == null || length <= 0) {
            return false;
        }
        // 所有数字都在0到n-1的范围内
        for (int i = 0; i < length; i++) {
            if (numbers[i] < 0 || numbers[i] > length - 1) {
                return false;
            }
        }
        // 扫描整个数组，当扫描到下标为 i 的数字时，首先比较该数字（m）是否等于 i，如果是，则接着扫描下一个数字；
        // 如果不是，则拿 m 与第 m 个数比较。如果 m 与第 m 个数相等，则说明出现重复了；
        // 如果 m 与第 m 个数不相等，则将 m 与第 m 个数交换，将 m "归位"，再重复比较交换的过程，直到发现重复的数
        for (int i = 0; i < length; i++) {
            while (numbers[i] != i) {  // 跳出循环的时候，已经number[i] == i， 即number[0] == 0  ------'归位'
                if (numbers[i] == numbers[numbers[i]]) {
                    duplication[0] = numbers[i];
                    return true;
                }
                int temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        return false;
    }

    // 方法二:哈希表 ,使用Hashset寻找重复数字
    public boolean Hduplicate(int[] num, int length, int[] duplication) {
        HashSet<Integer> hm = new HashSet<>();
        for (int i = 0; i < length; i++) {
            if (hm.contains(num[i])) {
                duplication[1] = num[i];
                return true;
            } else {
                hm.add(num[i]);
            }
        }
        return false;
    }

    // 方法三：排序
    public boolean duplicate1(int[] num, int length, int[] duplication) {
        Arrays.sort(num);
        for (int i = 0; i < length; i++) {
            if (num[i] == num[i + 1]) {
                duplication[2] = num[i];
                return true;
            }
        }
        return false;
    }
}

// 测试
public static void main(String[] args) {
        int[] arr = {2, 3, 1, 0, 2, 5, 3};
        int[] duplication = new int[3];
        int length = 7;
        L01_duplicate dp = new L01_duplicate();
        System.out.println("法一");
        System.out.println(dp.duplicate(arr, length, duplication));
        System.out.println(duplication[0]);
        System.out.println("法二");
        System.out.println(dp.Hduplicate(arr, length, duplication));
        System.out.println(duplication[1]);
        System.out.println("法三");
        System.out.println(dp.duplicate1(arr, length, duplication));
        System.out.println(duplication[2]);

    }
/**
法一
true
2
法二
true
2
法三
true
2
**/

时间复杂度O(n)