0287. Find the Duplicate Number
===============================
题目信息
--------
:题号: 0287
:难度: Medium
:主题: 数组、重复值、只读输入、常数空间
:原题: `LeetCode 0287 `_
:重点: 长度为 ``n+1`` 而取值只有 ``1..n``、唯一重复值可出现多次、不能修改数组
题目重述
--------
给定包含 ``n+1`` 个整数的数组 ``nums``,每个元素都位于 ``[1, n]``。题目保证只有一个不同的整数在数组中重复出现,但这个整数可能出现两次,也可能出现更多次。返回这个唯一的重复值。
``1 <= n <= 10^5``。答案值唯一,不要求返回重复位置或出现次数。必须把输入数组视为只读,不能通过排序、取负标记或交换元素来改变其内容;同时只允许使用常数级额外空间。题目的进阶要求整体运行时间不超过 ``O(n)``。
自建示例
--------
重复值出现两次:
.. code-block:: text
输入:nums = [2, 5, 1, 4, 3, 5]
输出:5
解释:数组长度为 6,因此 n = 5,所有值都在 1..5 中;只有 5 重复出现。
同一个值出现多次:
.. code-block:: text
输入:nums = [3, 1, 3, 4, 2, 3]
输出:3
解释:3 出现三次,其他出现过的值都没有重复;题目仍只要求返回重复值 3。
把数组看成函数图
----------------
把下标 ``i`` 的下一节点定义为 ``nums[i]``。由于每个值都在 ``1..n``,
从下标 0 出发后会进入有限节点集合;数组长度为 ``n+1`` 而可取值只有 ``n`` 个,
重复值使这条函数链出现环。环的入口正是重复值:不同的前驱路径最终在该值汇合,
而从入口继续跟随 ``nums`` 会循环。
用 Floyd 快慢指针找环入口:先让 ``slow`` 每次走一步、``fast`` 每次走两步,
在环内相遇;再把 ``slow`` 放回起点,两个指针都每次走一步,它们再次相遇的位置就是环入口。
全过程只读取数组,不需要修改元素或保存访问集合。
正确性说明
----------
有限函数图中,快慢指针进入环后相对距离每轮改变一个固定步长,必然相遇。设起点到环入口距离为 ``mu``,
相遇点到入口的环内距离为 ``d``;相遇关系说明 ``mu+d`` 是环长的整数倍,所以把一个指针移回起点后,
两指针分别走 ``mu`` 步会同时到达入口。入口对应的值就是唯一重复的数字,故返回正确。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int findDuplicate(std::vector& nums) {
int slow = nums[0];
int fast = nums[nums[0]];
while (slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};
代码分析
--------
快慢阶段和入口阶段各自为 ``O(n)``,总时间复杂度为 ``O(n)``;只保存两个下标,额外空间为 ``O(1)``。
算法依赖的是值域和长度形成的函数图,不依赖重复值只出现两次,因此也适用于题目允许的多次重复。