题目描述
给定一个长度为 n+1 的数组nums,数组中所有的数均在 1∼n 的范围内,其中 n≥1。
请找出数组中任意一个重复的数,但不能修改输入的数组。
样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。
返回 2 或 3。
算法1
二分法
由于数组中数字的范围是[1,n],而数组可以存储n+1个数,因此一定有重复的数字
可以定义min=1,max=n,mid = (min + max)/2,然后统计区间[min,mid]之间出现的数字的个数
若此个数大于mid - min + 1,则表示此区间一定有重复数字。反复二分,直到min == max
时间复杂度 $O(n*ln n)$
C++ 代码
class Solution {
public:
/*
* 不能修改数组,因此不能用置换法
* 此处采用二分法,实际上是一步步缩小min和max的差距
* 统计范围[min,mid]之间的数字个数
*/
int duplicateInArray(vector<int>& nums) {
// 注意:此处的min和max表示的数字的范围
int min = 1, max = nums.size() - 1;
while(min < max){
int mid = (min + max) >> 1;
int c = 0;
// 统计范围在[min,mid]的数字个数
for(int x : nums)
c += (x >= min && x <= mid);
if(c > mid - min + 1)
max = mid;
else
min = mid + 1;
}
return min;
}
};