剑指offer Q3 数组中重复的数字

数组中重复数字的问题，这道题考虑的是数组中的数字在一定的范围中，大致有两种情况：

1.数组长度大于等于数字的范围如：在一个长度为n的数组里的所有数字都在0～n-1的范围内。

2.数组长度小于数字的范围如：在一个长度为n的数组里的所有数字都在1～n-1范围内。

第一个问题解法：

会修改原始数据的解法：一个是借助快排，另一个是借助该数组的特性。

借助快速排序的方法就省略代码了，大致思路就是拍完序后，逐个检验数组中的数字是否和前后数字相同。

第一个借助数组长度大于等于数字的范围这一特性。

重排这个数组。从头到尾依次扫描这个数组中的每个数字。当扫描到下标为i的数字时，首先比较这个数字（用m表示）是不是等于i。如果是，则接着扫描下一个数字；如果不是，则再拿它和第m个数字进行比较。如果它和第m个数字相等，就找到了一个重复的数字（该数字在下标为i和m的位置都出现了）；如果它和第m个数字不相等，就把第i个数字和第m个数字交换，把m放到属于它的位置。接下来再重复这个比较、交换的过程，直到我们发现一个重复的数字。

以数组｛2，3，1，0，2，5，3｝为例来分析找到重复数字的步骤。数组的第0个数字（从0开始计数，和数组的下标保持一致）是2，与它的下标不相等，于是把它和下标为2的数字1交换得到结果｛1，3，2，0，2，5，3｝，再取数组的第0个数字1和下标为1的数字3比较，不相等则交换两个数字得到结果｛3，1，2，0，2，5，3｝，再取下标为0的数字3重复上述操作得到结果｛0，1，2，3，2，5，3｝这次完成后就可以发现数组中0，1，2，3的数字都与下标相等，第5个数字2与下标不相等但是和下标为2的数字相等那么就得到了一个重复数字2。
代码：

public static int getDuplication（int[] data）｛
    if（data＝＝null｜｜data.length<2）
        return -1;
    for(int i＝0；i<data.length；i++)
        while(data[i] !== i)
            ｛if（data[i] !== data[data[i]]）{
                  temp = data[i];
                  data[i] = data[data[i]];
                  data[data[i]] = temp;
                  }else{
                  return data[i];
                  }
              ｝
         return -1;
｝

第二个借助数组长度（数字个数）小于数字范围这一特性。

这个情况下肯定有数字是重复的。那么在这种情况下可以用二分法
进行二路归并。
代码：

public static int getDuplication(int[] data){
    if(data == null || data.length<2)
        return -1;
    int start = 0;
    int end = data.length-2;
    while(start<=end){
        int middle = (end-start)/2+start;
        int count = countRange(data.start,middle);
        if(start==end){
            if(count>1)
                return start;
            else
                return -1;
        }
        if(count>end-start+1)
            end = middle;
        else
            start = middle+1;
    }  
    return -1;
}

public static int countRange(int[] data，int start，int end){
    int count = 0;
    for(int i=0;i<data.length;i++){
         if(data[i]<end&&data[i]>start){
            count++;
        }
    }
     return count;
}