题目
思路一 – 二分
若 nums.length = n + 1,那么 n 代表最大的数,即数的范围是[1,n]。如果我们指定一个数字 c,求其在 nums 中小于等于 c 的个数(cnt)。“个数”是具有二段性质的,如下方数据样例,当 c 落在 i 区间时,cnt == c;当 c 落在 j 区间时,cnt > c。故,可利用该二段性进行二分搜索。
values 1 2 3 3 4 c 1 2 3 4 cnt 1 2 4 5 --i--- ------j-----
代码
class Solution {
public:
int findDuplicate(vector<int>& N) {
int n=N.size()-1;
int l=1,r=n,m,cnt;
bool check;
while(l<r) {
m=(l+r)>>1;
check=false;
cnt=0;
for (auto& c:N) if(m>=c) ++cnt;
if (cnt>m) r=m;
else l=m+1;
}
return l;
}
};
思路二 – 快慢指针
当数组的索引 i 看成当前节点的指针,把 nums[i] 看成是当前节点指向下一个节点的指针。那么,可视 nums 为一个单向链表。简单尝试,当有一个数字重复时,该链表是有环的。即将问题转变为判断链表是否有环。故,可以用快慢指针。证明见:LeetCode 题解
代码
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = 0, fast = 0;
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow == fast) break;
}
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};
欢迎分享,引用。若转载,请联系我,谢谢配合。 本文地址:https://qoogle.top/xiaoxu-tutorial-leetcode-287-find-the-duplicate-number/
[…] 小旭讲解 LeetCode 287. 寻找重复数 […]