【剑指】数组中的重复数字

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

简析：

在看到重复数字，重复次数无法确定的时候（m >= 2），我们首先想到的办法是排序。

排序可以将相同的数字汇聚在一起，再进行一次遍历，如果前后两个元素恰好相同，这个元素就是重复的。

如果借助工具，我们可以使用HashMap计数，遍历一遍所有的元素，对应的值作为key，出现次数作为value计数，这样再遍历一次Map，找到value大于等于2的就是重复元素。

还有一种比较高效的方式，就是交换位置。因为所有数字都在 0～n-1 的范围内，将对应的元素放置到对应的位置上，例如，2放在index = 2的位置上。如果第i个位置上的元素e不是i，那么就要把第e上的元素和第i个位置进行交换，如果发现e恰好等于a[e], 说明是重复元素。

我们发现，每交换一次位置就归置了一个数字到对应的位置。

public int firstRepeat(int[] array){
    if (array == null || array.length <= 1){
        return -1;
    }
 
    // 开始遍历每一个位置
    for (int i = 0; i < array.length){
        // 被遍历的i位置上的元素必须是i，否则交换
        while (array[i] != i){
            int e = array[i];
            // 待交换位置和当前位置的元素相同
            if (array[i] == array[e]){
                // 直接返回
                return e;
            }
            // 不匹配时，交换位置
            swap(array, i, e);
        }
    }
    return -1;
}
 
public void swap(int[] array, int source, int dest){
    int temp = array[source];
    array[source] = array[target];
    array[target] = temp;
}