算法修炼50、数组中重复的数字

题目描述：

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

  解题思路：

  解决这个问题最简单的办法是将输入的数组排序，从排序的数组中找出重复的数字只需要从头到尾扫描即可，所以先排序再查找的时间复杂度主要就取决于排序算法，一般为O(nlogn)。

  还是那句话：“最容易想到的往往不是最佳解法”。

  进一步考虑，我们也不难想到借助空间换时间的思路，通过哈希表来解决。从头到尾按顺序扫描整个数组，依次将其存入哈希表，每扫描到一个元素，都可以用O(1)的时间判断哈希表里是否已经存在该值，如果不存在，就将其加入哈希表，继续扫描下一个，如果存在，那么该元素就是第一个重复的数字。这个算法的时间复杂度是O(n)，但很显然这个效率的提升也是用空间换来的。

  因此，我们希望得到一种不消耗额外空间的算法，也就是本题的第三种解法：数组重排。由于题目中告诉我们所有的数字都在0到n-1的范围内，因此如果没有重复，那么所存储的值也正好是0到n-1这n个数字，我们把原数组重新排列为一个元素和对应下标值相同的数组。具体思路如下：

  从头到尾扫描整个数组中的数字，当扫描到下标为i的数字时，首先比较这个数字（用m表示）是不是等于下标i，如果是，接着比较下一个数字；如果不是，则将其与第m个数字比较，若与第m个数字相同，则说明它就是一个重复数字，如果不同，就将其与第m个数字进行交换，也就是把它放到自己应在的位置去。重复这个过程，直到该位置上的数与下标相同为止。

  该算法看起来是两层循环，但是每个数字最多进行两次交换就会找到属于自己的位置，因为总的时间复杂度还是O(n)，不需要额外内存。

  举例：

  以{2,3,1,0,2,5,3}为例：

• 0(索引值)和2(索引值位置的元素)不相等，并且2(索引值位置的元素)和1(以该索引值位置的元素2为索引值的位置的元素)不相等，则交换位置，数组变为：{1,3,2,0,2,5,3}；
• 0(索引值)和1(索引值位置的元素)仍然不相等，并且1(索引值位置的元素)和3(以该索引值位置的元素1为索引值的位置的元素)不相等，则交换位置，数组变为：{3,1,2,0,2,5,3}；
• 0(索引值)和3(索引值位置的元素)仍然不相等，并且3(索引值位置的元素)和0(以该索引值位置的元素3为索引值的位置的元素)不相等，则交换位置，数组变为：{0,1,2,3,2,5,3}；
• 0(索引值)和0(索引值位置的元素)相等，遍历下一个元素；
• 1(索引值)和1(索引值位置的元素)相等，遍历下一个元素；
• 2(索引值)和2(索引值位置的元素)相等，遍历下一个元素；
• 3(索引值)和3(索引值位置的元素)相等，遍历下一个元素；
• 4(索引值)和2(索引值位置的元素)不相等，但是2(索引值位置的元素)和2(以该索引值位置的元素2为索引值的位置的元素)相等，则找到了第一个重复的元素。

  编程实现（Java）：

public class Solution {
    // Parameters:
    // numbers:     an array of integers
    // length:      the length of array numbers
    // duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    // Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    // 这里要特别注意~返回任意重复的一个，赋值duplication[0]
    // Return value:true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers==null || length