算法
(分治,抽屉原理) O(nlogn)
复杂度
时间复杂度:每次会将区间长度缩小一半,一共会缩小 O(logn) 次。每次统计两个子区间中的数时需要遍历整个数组,时间复杂度是 O(n)。所以总时间复杂度是 O(nlogn)。
空间复杂度:代码中没有用到额外的数组,所以额外的空间复杂度是 O(1)。
C++ 代码
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int n = nums.size()-1;
int low = 1, high = n, mid, lc;
while(low < high){
mid = (low + high) / 2;
lc = countLowToHigh(nums, low, mid);
if(lc > (mid - low + 1))
high = mid;
else
low = mid + 1;
}
}
// 统计from-to范围内有几个数
int countLowToHigh(vector<int>& nums, int from, int to){
int c = 0;
for(auto x : nums){
if(x >= from && x <= to) c++;
}
return c;
}
};