原创博文，转载请注明出处！
# 题目
在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或者3。
# 思路
借鉴二分查找的思想，将数字1~n拆分成1~m和m+1~n两部分，如果数字范围1~m中数字个数大于m，则重复数字在1~m中间，否则重复数字一定在数字范围m+1~n中。基于二分查找法不能找到全部的重复数字，例如{2,2,3,3,4,5,6,7}中数字区间为1~2的范围内2出现两次，但1没有出现，不能确定是每个数字出现一个还是某个数字出现两次。
# 代码
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4 class Solution{
5 public:
6 int duplication(vector<int> vec)
7 {
8 // 空数组
9 int length = vec.size();
10 if(vec.size() == 0)
11 return -1;
12
13 // 数字超界
14 for(int i =0;i<length;++i)
15 {
16 if(vec[i]<1 || vec[i]>length-1)
17 return -1;
18 }
19 // 定义数字范围
20 int begin = 1;
21 int end = length-1;
22
23 // 指定数字范围内的数字个数
24 while(begin<=end)
25 {
26 // 计算数字范围的中点
27 int mid = (begin + end)>>1;
28
29 // 统计指定数字范围内的数字个数
30 int count = countrange(vec,begin,mid,length);
31
32 if(end > begin)
33 {
34 // 更新数字范围
35 if(count>(mid - begin + 1))
36 end = mid;
37 else
38 begin = mid + 1;
39 }
40 else
41 {
42 if(count > 1)
43 return begin;
44 else
45 break;
46 }
47 }
48
49 return -1;
50 }
51
52 int countrange(vector<int> vec,int begin,int end,int length)
53 {
54 int count=0;
55 for(int i=0;i<length;++i)
56 {
57 if(vec[i]>=begin && vec[i]<=end)
58 ++count;
59 }
60
61 return count;
62 }
63 };
64
65 int main()
66 {
67 vector<int> vec ;
68 vector<int> vec1 = {1,2,3,4,5,6,7};
69 vector<int> vec2 = {1,1,2,3,4,5,6};
70 vector<int> vec3 = {2,2,3,3,4,5,6};
71
72
73 Solution solution;
74 cout<<solution.duplication(vec)<<endl;
75 cout<<solution.duplication(vec1)<<endl;
76 cout<<solution.duplication(vec2)<<endl;
77 cout<<solution.duplication(vec3)<<endl;
78
79 return 0;
80 }
# 复杂度
时间复杂度为O(nlogn)，空间复杂度为O(1)
# 测试用例
- 空数组
- 数字超界
- 数组中包含一个重复数字
- 数组中包含多个重复数字