试题3：数组中重复的数字

题目：

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

分析：

1. 最容易想到的思路是暴力查找，两层循环，那样的时间复杂度为O(n²)空间复杂度为O(1)；
2. 其次可以将数组进行排序然后进行查找，将数组排序的最佳算法的空间复杂度为O(nlogn)
3. 该数组比较特殊。长度为n的数组，数字范围是0~n-1，如果没有重复的数字，那么可以实现的一种排序是元素和其对应下标相等。如果有重复，就会导致多个元素对应同一个下标。{2，3，1，0，2，5，3}以该数组为例，从下标为0的元素开始，元素2不等于其下标，所以它应该放在下标为2的位置，将元素2与下标为2的元素0进行交换得到新的数组
   {0，3，1，2，2，5，3}。下标为0的元素已经为0了，继续看下标为1的元素为3应该和下标为3的元素互换，数组变成
   {0，2，1，3，2，5，3}，下标为1的元素为2应该和下标为2的元素互换数组变成
   {0，1，2，3，2，5，3}。下标为1的元素已经为1，继续看下标为2的元素2和下标为3的元素，已经满足条件。发现下标为4的元素2等于下标为2的元素，找到一个重复的元素，返回true。
   虽然有两层循环，但是最多交换两次即可实现下标与元素的的对应（如果可能），该算法的复杂度为O(n)。

#include <iostream>
using namespace std;
bool duplicate(int numbers[],int length,int *duplication){
    if(numbers == nullptr || length <= 0)//长度异常
        return false;
    for(int i = 0 ; i <= length - 1; i++){//元素异常
        if( numbers[i] < 0||numbers[i] >length - 1){
            return false;
        }
    }
    for(int i = 0 ; i <= length - 1 ; 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;
}
void print(int numbers[],int length,int *duplication){
    if(duplicate(numbers,length,duplication))
            cout<<"重复数字为："<<*duplication<<endl;
        else
            cout<<"无重复数字"<<endl;
}

int  main(){
    int array[] = {1,2,4,5,3,2};
    int duplication;
    cout<<"数组{1,2,4,5,3,2}中是否有重复的数字:";
    print(array,sizeof(array)/sizeof(array[1]),&duplication);
    int duplication2;
    int array2[] = {1,2,4,5,3,-2};
    cout<<"数组{1,2,4,5,3,-2}中是否有重复的数字:";

    print(array2,sizeof(array2)/sizeof(array2[1]),&duplication2);
    int duplication3;
    int array3[] = {1,2,4,5,3,1};
    cout<<"数组{1,2,4,5,3,1}中是否有重复的数字:";
    print(array3,sizeof(array3)/sizeof(array3[1]),&duplication3);
    return 0;
}

运行结果