题目：
在一个长度为n的数组里所有的数字都在0~n-1的范围里。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中的任意一个重复的数字。例如输入长度为7的数组{2，3，1，0，2，5，3}，那么对应的的输出是重复的数字2或者3。
分析：
- 最容易想到的思路是暴力查找，两层循环，那样的时间复杂度为O(n2)空间复杂度为O(1)；
- 其次可以将数组进行排序然后进行查找，将数组排序的最佳算法的空间复杂度为O(nlogn)
- 该数组比较特殊。长度为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;
}
运行结果
