数组a共n+1个元素，元素取值范围1~n，返回数组中重复的元素之一
题目条件限定了数组中一定有重复元素，可以对每个可能的取值1~n计算出现次数。或者划分取值范围为1~m，m+1~n，计算两个取值区间在数组a中出现的总次数，如果范围为1~m的统计次数大于m，说明有重复。但如果有某个符合取值范围的元素数组中出现了0次，那么可能为某个重复次数为两次的元素提供了隐蔽条件，这个重复的元素也无法找出，但说明另一个取值范围内也有元素是重复的
int cntRange(int* a, int len, int st, int end) {int cnt = 0;for (int i = 0; i < len; i++) {if (a[i] <= end && a[i] >= st)cnt++;}return cnt;}int func(int* a, int len) {int st = 1, end = len - 1, mid, cnt;while (st <= end) {mid = (st + end) / 2;cnt = cntRange(a, len, st, mid);if (st == end) {if (cnt > 1)return st;else return -1;}if (cnt > mid - st + 1)end = mid;else st = mid + 1;}}void test02() {//int a1[] = { 49,38,65,97,76,13,27,49 };int a[] = { 2,3,5,4,4,2,6,7 };//for (const int i : a)cout << i << ' '; cout << endl;cout << func(a, sizeof(a) / sizeof(*a)) << endl;}
