找出数组中重复的数字

题目：

在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但是不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7,的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数组2或者3。（n个元素，n种可能的取值）

方法一：对数组进行排序，然后再查找排序中重复的元素

public static void getDuplicateBySort(int[] arr) {
    if (null == arr || arr.length == 0) {
        return;
    }

    for (int i = 0; i < arr.length; i++) {
        if (arr[i] < 0 || arr[i] > arr.length - 1) {
            return;
        }
    }
    // 排序，这里直接使用了工具类
    Arrays.sort(arr);

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

        if (i == arr.length - 1) {
            break;
        }

        if (arr[i] == arr[++i]) {
            System.out.println(arr[i]);
        }
    }
}

方法二：使用 list，如果遇到重复元素就输出，不重复就添加

public static void getDuplicateByList(int[] arr) {
    if (null == arr || arr.length == 0) {
        return;
    }

    for (int i = 0; i < arr.length; i++) {
        if (arr[i] < 0 || arr[i] > arr.length - 1) {
            return;
        }
    }

    // 这里也可以使用map、set集合
    List list = new ArrayList(arr.length);

    for (int i : arr) {
        if (list.contains(i)) {
            System.out.println(i);
            continue;
        }

        list.add(i);
    }
}

方法三： 《剑指offer》优解

因为列表总共有n个元素，所有元素可能取到的元素有0~n-1，共n种。如果不存在重复的数字，那么排序后数字 i 将会出现在下标为 i 的位置。现在让我们重新扫描数组，

• 当扫描到下标为i的数字时，首先比较这个数字（记为m）与 i 是否相等：
  • 如果是，继续扫描下一个元素，
  • 如果不是，则再拿它与第m个数字比较：
    • 如果它和第m个数字相同，就找到了一个重复的元素；
    • 如果不同，就将m与第m个数字互换。接下来继续重头开始，重复换这个比较。

public static void getDuplicateByCompare(int[] arr) {
    
    if (null == arr || arr.length == 0) {
        return;
    }

    for (int i = 0; i < arr.length; i++) {
        if (arr[i] < 0 || arr[i] > arr.length - 1) {
            return;
        }
    }

    Arrays.sort(arr);

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

        while (arr[i] != i) {
            if (arr[i] == arr[arr[i]]) {
                System.out.println(arr[i]);
                break;
            }

            int temp = arr[i];
            arr[i] = arr[temp];
            arr[temp] = temp;
        }
    }
}