小旭讲解 LeetCode 287. Find the Duplicate Number
小旭讲解 LeetCode 287. Find the Duplicate Number

题目

LeetCode 287. 寻找重复数

思路一 – 二分

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/
0 0 vote
Article Rating
Subscribe
提醒
guest
1 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments

[…] 小旭讲解 LeetCode 287. 寻找重复数 […]