试题3_2:数组中重复的数字（不改动数组）

题目：

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

1. 要求不能修改数组可以自己定义一个辅助的数组。这一方法是使用空间换取时间消耗。时间和空间复杂度均为O(n)。实现代码如下：

#include <iostream>
using namespace std ;
int findDup(int numbers[], int length){
    int *array = new int[length];
    if (numbers == nullptr || length <= 0 )//数组非空
    {
        return -1;
    }

    for (int i = 0; i < length - 1; ++i)
    {
        if (numbers[i] == array[numbers[I]])
        {
            return numbers[I];
        }
        array[numbers[i]] = numbers[I];
    }
    return -1;
}
void print(int numbers[],int length){
    int dup;
    if ((dup = findDup(numbers,length)) > 0)
    {
        cout<<"重复数字为："<<dup<<endl;
    }else{
        cout<<"异常或无重复数字"<<endl;
    }
}
int main(int argc, char const *argv[])
{
    int numbers[] = {2,3,5,4,3,2,6,7};
    cout<<"测试用例1（多个重复数字）";
    print(numbers,sizeof(numbers)/sizeof(int));

    int numbers2[] = {2,3,5,4,1,8,6,7};
    cout<<"测试用例2（无重复数字）";
    print(numbers2,sizeof(numbers2)/sizeof(int));
    
    int numbers3[] = {};
    cout<<"测试用例3（空指针）";
    print(numbers3,sizeof(numbers3)/sizeof(int));
    return 0;
}

运行结果

2. 类二分搜索的方法。将数组元素1_{7以4为中心分为两部分，分别统计1}4这四个数字出现的总次数和5_{7这四个数字的出现总次数。统计发现1}4之间的数字出现了5次那么重复数字必定在其中。
   再将1_{4划分为两部分1}2和3_{4再行，统计即可得出在3}4中有重复数字。再把3和 4划分为两部分即可找到出现两次的数字。统计区间数字出现总次数需要的时间为O(n)，二分的次数为O(logn)，所以时间复杂度为O(nlogn)。空间复杂度为O(1)
   上述思想代码实现：

#include <iostream>
using namespace std;
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;
}
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;

}
void print(int numbers[],int length){
    int dup;
    if((dup =getDuplication(numbers,length)) > 0){
        cout<<"重复数字为："<<dup<<endl;
    }else{
        cout<<"无重复数字或非法输入"<<endl;
    }
}
int main(){
    
    int array[] = {2,3,5,4,3,2,6,7};
    cout<<"测试用例1（有重复数字）：";
    print(array,sizeof(array)/sizeof(int));
    
    int array1[] = {};
    cout<<"测试用例2（空指针）：";
    print(array1,sizeof(array1)/sizeof(int));
    
    int array2[] = {1,2,4,5,6,7,3,8};
    cout<<"测试用例2（不含重复数字）：";
    print(array2,sizeof(array2)/sizeof(int));

    return 0;
}

运行结果