題目：

在一個長度為n+1的數(shù)組里的所有數(shù)字都在1到n的范圍內(nèi)煮甥，所以數(shù)組中至少有一個數(shù)字是重復(fù)的穴墅。請找出數(shù)組中任意一個重復(fù)的數(shù)字颤难，但不能修改輸入的數(shù)組爽室。例如堕油，如果輸入長度為8的數(shù)組{2, 3, 5, 4, 3, 2, 6, 7}，那么對應(yīng)的 輸出是重復(fù)的數(shù)字2或者3。
分析：

1. 要求不能修改數(shù)組可以自己定義一個輔助的數(shù)組掉缺。這一方法是使用空間換取時間消耗卜录。時間和空間復(fù)雜度均為O(n)。實現(xiàn)代碼如下：

#include <iostream>
using namespace std ;
int findDup(int numbers[], int length){
    int *array = new int[length];
    if (numbers == nullptr || length <= 0 )//數(shù)組非空
    {
        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<<"重復(fù)數(shù)字為："<<dup<<endl;
    }else{
        cout<<"異晨裘鳎或無重復(fù)數(shù)字"<<endl;
    }
}
int main(int argc, char const *argv[])
{
    int numbers[] = {2,3,5,4,3,2,6,7};
    cout<<"測試用例1（多個重復(fù)數(shù)字）";
    print(numbers,sizeof(numbers)/sizeof(int));

    int numbers2[] = {2,3,5,4,1,8,6,7};
    cout<<"測試用例2（無重復(fù)數(shù)字）";
    print(numbers2,sizeof(numbers2)/sizeof(int));
    
    int numbers3[] = {};
    cout<<"測試用例3（空指針）";
    print(numbers3,sizeof(numbers3)/sizeof(int));
    return 0;
}

運行結(jié)果

2. 類二分搜索的方法艰毒。將數(shù)組元素1_{7以4為中心分為兩部分，分別統(tǒng)計1}4這四個數(shù)字出現(xiàn)的總次數(shù)和5_{7這四個數(shù)字的出現(xiàn)總次數(shù)搜囱。統(tǒng)計發(fā)現(xiàn)1}4之間的數(shù)字出現(xiàn)了5次那么重復(fù)數(shù)字必定在其中丑瞧。
   再將1_{4劃分為兩部分1}2和3_{4再行，統(tǒng)計即可得出在3}4中有重復(fù)數(shù)字蜀肘。再把3和 4劃分為兩部分即可找到出現(xiàn)兩次的數(shù)字绊汹。統(tǒng)計區(qū)間數(shù)字出現(xiàn)總次數(shù)需要的時間為O(n)，二分的次數(shù)為O(logn)扮宠，所以時間復(fù)雜度為O(nlogn)西乖。空間復(fù)雜度為O(1)
   上述思想代碼實現(xiàn)：

#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<<"重復(fù)數(shù)字為："<<dup<<endl;
    }else{
        cout<<"無重復(fù)數(shù)字或非法輸入"<<endl;
    }
}
int main(){
    
    int array[] = {2,3,5,4,3,2,6,7};
    cout<<"測試用例1（有重復(fù)數(shù)字）：";
    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（不含重復(fù)數(shù)字）：";
    print(array2,sizeof(array2)/sizeof(int));

    return 0;
}

運行結(jié)果