找出数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3
下面是几个解决这个问题的思路
解决这个问题的简单的办法是把输入的数组排序。然后从排序的数组中找出重复的元素。从头到位扫描一遍即可。用一个变量始终记录着上一个元素。比较当前元素和上一个元素。 排序一个长度为n的数组需要O(nlogn)的时间。
我们还可以使用Hash表来解决这个问题。创建一个Hash表，从头到尾遍历一遍。Hash表没有的话则加入hash，有的话则Value+1。这个算法的时间复杂度是O(n),但是它提高时间效率是以创建一个大小为O(n)的哈希表为代价的。
-
还有一种方法是我们注意到0-n-1的范围，如果没有重复数字，那么排序之后数字i将出现在下标i的位置上，但是如果存在的话，某些位置就可能存在多个数组，有的位置就可能不存在数字。
解决这个问题的思路。从头到尾扫描，比较m和位置i的关系。如果相等则扫描下一个，如果不等的话，m和下标m的元素互换。然后继续执行。先比较位置和数字自身的关系，如果相同则扫描下一个。如果等于的话则找到了。如果不等的话，则继续互换。
bool dumplcate(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) {
return false;
}
}
for (int i=0; i<length; i++) {
while (numbers[i] != i) { //只要下标和当前原色不相等，就继续执行
int m = numbers[i];
if (m == numbers[m]) {
*duplication = m;
return true;
}
int transfer = numbers[m];
numbers[i] = transfer;
numbers[m] = m;
}
}
return false;
}