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

题目

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/