LeetCode100 - 寻找重复数 | 很多时候不懂事

📝 题目描述

给定一个包含 n + 1 个整数的数组 nums，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数，返回 这个重复的数。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 $O(1)$ 的额外空间。

示例：

示例 1：

输入：nums = [1,3,4,2,2]
输出：2

示例 2：

输入：nums = [3,1,3,4,2]
输出：3

示例 3 :

输入：nums = [3,3,3,3,3]
输出：3

提示：

1 <= n <= 10^5
nums.length == n + 1
1 <= nums[i] <= n
nums 中只有一个整数出现两次或多次，其余整数均只出现一次

💡 解题思路

方法一：快慢指针

这道题的关键，是把数组中的重复数转化为链表的环入口，这样就能使用 Floyd 快慢指针算法解决问题。我们约定 每个下标 i 是一个节点，nums[i] 是它指向的下一个节点。也就是说，链表里通常写的 p = p->next，在这里就变成了：

1	p = nums[p];

以 nums = [1,3,4,2,2] 为例：

下标`i`	`nums[i]`	指向关系
0	1	0→1
1	3	1→3
2	4	2→4
3	2	3→2
4	2	4→2

从下标 0 出发，会走出下面的路径。图中的数字代表下标：

不难发现，环入口恰好是重复数 2。这是因为，所有 nums[i] 都在 [1, n] 内，因此每次跳转都合法，也永远可以继续走。节点数量有限，所以不断跳转，必然会再次遇到走过的节点形成环；又因为没有节点能够指向 0，因为数组里没有值 0。所以，从 0 出发，一定会先经过一段路径，再进入环。

这个环入口，会被两个不同的节点指向：

一个是进入环之前的最后一个节点。
一个是环内绕一圈回来时的前一个节点。

在示例里，这两个节点是下标 3 和下标 4：

1 2	nums[3] == 2; nums[4] == 2;

两个不同位置存放着相同的值，所以环入口对应的数字就是重复数。题目保证只有一个数重复，因此找到这个入口，就找到了答案。即使一个数字出现超过两次，这个结论也成立。

综上所述，我们的算法可以这样规划，算法分成两个阶段：

两个指针从 0 出发，慢指针每次走一步，快指针每次走两步，直到相遇。
相遇后，把其中一个指针移回 0，另一个留在相遇位置。然后两个指针都每次走一步，再次相遇的位置就是环入口。

第一步不难理解，两个指针都进入环后，快指针每轮相对慢指针多走一步，就像跑圈时追赶一样，一定会相遇（这里相遇的位置不一定是环入口）。这里解释一下第二步，为什么重置以后，一定会在环入口相遇。

假设：

从起点 $0$ 到环入口，需要走 $a$ 步。
环的长度为 $L$ 。
第一阶段相遇时，慢指针已经走了 $t$ 步，快指针就走了 $2t$ 步。

它们从同一起点出发，最终在环内同一位置相遇，说明快指针比慢指针多走的距离是若干整圈：

$2t−t=kL⇒t=kL$

慢指针到达相遇位置之前，先走了 $a$ 步进入环，再在环内走了 $t-a$ 步。所以，从相遇位置再走 $a$ 步，累计在环内走过的步数就是：

$(t−a)+a=t=kL$

恰好是整圈数，因此回到环入口。

与此同时，重置到 $0$ 的指针走 $a$ 步，也恰好到达环入口。所以两者会在那里相遇；在这之前，一个在环外，一个在环内，不可能相遇。

方法二：二分查找

我们定义 $cnt[i]$ 表示 $nums$ 数组中小于等于 $i$ 的数有多少个。

假设我们重复的数是 $target$ ，那么 $[1,target−1]$ 里的所有数满足 $cnt[i]≤i$ ， $[target,n]$ 里的所有数满足 $cnt[i]>i$ ，具有单调性。

以示例 [1,3,4,2,2] 为例，我们列出每个数字的 $cnt$ 值：

nums	1	2	3	4
cnt	1	3	4	5

示例中重复的整数是 $2$ ，我们可以看到 $[1,1]$ 中的数满足 $cnt[i]≤i$ ， $[2,4]$ 中的数满足 $cnt[i]>i$ 。

如果知道 $cnt[]$ 数组随数字 $i$ 逐渐增大具有单调性（即 $target$ 前 $cnt[i]≤i$ ， $target$ 后 $cnt[i]>i$ ），那么我们就可以直接利用二分查找来找到重复的数。

🔧 代码实现

1、快慢指针

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int fast = 0, slow = 0;
        // 第一阶段：找到环内的相遇点
        // 初始时两个指针相等，所以先移动，再判断
        do {
            // fast 一次走两步
            fast = nums[nums[fast]];
            // slow 一次走一步
            slow = nums[slow];
        } while (fast != slow);

        // 第二阶段：找到环入口
        fast = 0;
        while (fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }
        
        return fast;
    }
};

2、二分查找

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        // 数字范围为 1 到 n
        int left = 1, right = n - 1, ans = -1;
        while (left <= right) {
            // 二分法求中点
            int mid = left + (right - left) / 2;
            int cnt = 0;
            // 统计小于等于 mid 的元素数量
            for (int i = 0; i < n; i++) {
                if (nums[i] <= mid) {
                    cnt++;
                }
            }
            if (cnt <= mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
                // 记录答案
                ans = mid;
            }
        }
        return ans;
    }
};

📊 复杂度分析

1、快慢指针

时间复杂度： $O(n)$ ，两个阶段都只需线性数量的跳转。
空间复杂度： $O(1)$ ，只使用两个指针变量。

2、二分查找

时间复杂度： $O(nlogn)$ ，其中 $n$ 为 $nums$ 数组的长度。二分查找最多需要二分 $O(logn)$ 次，每次判断的时候需要 $O(n)$ 遍历 $nums$ 数组求解小于等于 $mid$ 的数的个数。
空间复杂度： $O(1)$ ，我们只需要常数空间存放若干变量。

🎯 总结

核心思想：将数组视作链表，转化为链表求环的思想需要记住。