题目：在一个长度为n+1的数组里的所有数字都在1~n的范围，找出任意一个重复的数字，但不能修改数组。例如数{2 3 5 4 3 2 6 7 },对应的输出是2或者3
解法一：扫一便数组，map容器去统计每个数字出现的次数
解法二：将区间二分，看那边的数字出现的次数多就继续去哪边查找重复的数字，例如{ 2 3 5 4 3 2 6 7 }
数组的长度为8，数据都在1~7的范围，将数字分成1~4和5~7两段，1~4在数组中出现5次， 5~7的数字在数组中出现3次， 所以重复的数字在1~4这一段，同理，1~4分为1~2和3~4两段，1~2的数字在数组中出现2次，3~4的数字在数组中出现3次，显然重复的数字在3~4.3和4肯定有一个重复了， 此时再分别统计这两个数字在数组中出现的次数即可得到答案。
//统计在start到end范围的数个个数 int countRange(int numbers[], int start, int end, int length) { if(numbers == nullptr) return 0; int ans = 0; for(int i = 0; i < length; i++) { if(numbers[i] >= start && numbers[i] <= end) ans++; } return ans; } int getDuplication(int numbers[], int length) { if(length <= 0 || numbers == nullptr)//空指针或者数组长度为0 return -1; for(int i = 0; i < length; i++) { if(numbers[i] <1 || numbers[i] > length - 1) { //cout<<"hehe"<<endl; //system("pause"); return -1; }//判断数据是否在1-length - 1; } int start = 1, end = length - 1; while(start <= end) { int mid = start + ((end - start )>>1); int count = countRange(numbers, start, mid, length); //cout<<count<<endl; if(end == start )//特判区间只是一个数字的时候 { if(count > 1) return start; else { break; }//无重复 } if(count > (mid - start + 1)) end = mid;//在1-mid有重复 else start = mid + 1;//mid+1-end有重复了 } return -1;//无重复的数字 }
