算法1 二分数值区间
时间复杂度 $O(nlogn)$
空间复杂度 $O(1)$
因为目标数字所在区间已知,而且根据抽屉原理可以比较方便地判别一段区间内是否存在重复的数,因此利用二分搜索的方法可以确定重复的数。
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int l = 1, r = nums.size()-1;
int mid;
while(l<r){
mid = l+r>>1;
int s=0;
for(auto &c:nums) s+=c>=l && c<=mid;
if(s>mid-l+1) r = mid;
else l = mid+1;
}
return l;
}
};
算法2 模拟链表+判环
将数组中的元素值作为下标,链接到下一个元素,若出现重复数字,则所连成的链表存在回路。
比如: [3,2,3,1,4,5]
写成链表的形式为: $3 \rightarrow 1 \rightarrow 2 \rightarrow 3$
判环以及找环路出口利用快慢指针即可。
时间复杂度 $O(n)$
空间复杂度 $O(1)$
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int f = 0, s = 0;
while(f==0 || f!=s){
f=nums[nums[f]];
s=nums[s];
}
f=0;
while(f!=s){
f=nums[f];
s=nums[s];
}
return s;
}
};