c++实现找数组中的重复数字+不改变数组的找重复数字的二分查找法

题目描述：找出数组中重复的数字

首先说明：不同的要求使用的函数是不一样的，如果只要求判断数组是否含有重复数字，并找出其中的任意一个可以使用下面的两种方法，如果找出每一个出现的重复数字还是得进行排序，遍历。

在一个长度为n的数组中，所有数字都在0~n-1的范围内，数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次，请找出数组中任意一个重复数字，如输入长度为7的数组arr[]={2,3,1,0,2,5,3}，那么对应输出是重复数字2,3
分析：简单的方法就是对数组整个进行sort排序，然后for循环遍历数组，如果前后两个数相等那么这个数组就有重复数字。

如果数组的前提的数字范围在0~n-1的范围内，在不用排序算法的前提下可以使用下列方法：

看数组中的第i个数m，如果i!=m说明m是不属于排序后i这个坑的，那么就找到m的坑也就是数组中的第m个值，如果第m个值不等于m，则交换两个值，如果相等则说明他就是那么重复值，说到这里可能还是很模糊的概念，那么我们来具体画一下数组重排图解：

bool duplicate(int numbers[],int length,int *duplication){
    if(numbers==nullptr||length<=0){
        return false;
    }
    for(int i=0;i<length;i++){
        if(numbers[i]<0||numbers[i]>length-1)
            return false;
    }
    for(int i=0;i<length;i++){
        while(numbers[i]!=i){
            if(numbers[i]==numbers[numbers[i]]){
                *duplication=numbers[i];
                return true;
            }
            int temp=numbers[i];
            numbers[i]=numbers[temp];
            numbers[temp]=temp;
        }
    }
    return false;
}

以上代码来自剑指offer，亲测有效，下面来说明一下代码实现的功能：

1. 首先代码的返回值是bool类型变量，如果返回true说明原数组中有重复数字，反之没有；
2. 代码中第一个参数是需要重排的数组，第二个参数是数组的长度，第三个参数是我们返回的出现重复的数字，使用方法：我们可以在调用的时候先定义一个int duplication；调用的时候： duplicate(arr,7,&duplication)；
3. 这个函数只能返回一个重复的数字。
4. 代码的时间复杂度为O(n)。

如果我们在题目中要求不可以改变数组呢？

最容易想到的方法就是我们创建一个辅助数组，在遍历数组的同时将数据复制到辅助数组中，需要O(n)的辅助空间，在不需要辅助空间的情况下可以使用如下办法：

题目描述：在一个长度为n+1的数组中所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复数字，但不能修改输入的数组，例如，如果输入长度为8的数组arr[]={2,3,5,4,3,2,6,7}，那么对应的输出是重复数字2或者3。

1. 把1~n的数字从中间的数字m分为两部分，前面一半为1–m，后面一半为m+1–n。
2. 如果1~m的数字的数目超过m，前半段区间里一定包含重复的数字。
3. 否则另一半包含重复的数组。

以上述数组为例：
把数组分为1–4的部分和5–8的部分，1–4的部分数字出现了5次，则在这一部分一定有重复数字，同样再分为1–2和3–4的部分，1–2的部分数字出现了2次，不用管，3–4的部分出现3次，则重复数字就在这两个数字中出现
代码如下：

int countRange(const int* numbers, int length, int start, int end);
int getDuplication(const int* numbers, int length)
{
    if(numbers == nullptr || length <= 0)
        return -1;

    int start = 1;
    int end = length - 1;
    while(end >= start)
    {
        int middle = ((end - start) >> 1) + start;
        int count = countRange(numbers, length, start, middle);
        if(end == start)
        {
            if(count > 1)
                return start;
            else
                break;
        }

        if(count > (middle - start + 1))
            end = middle;
        else
            start = middle + 1;
    }
    return -1;
}

int countRange(const int* numbers, int length, int start, int end)
{
    if(numbers == nullptr)
        return 0;

    int count = 0;
    for(int i = 0; i < length; i++)
        if(numbers[i] >= start && numbers[i] <= end)
            ++count;
    return count;
}