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)``。 算法依赖的是值域和长度形成的函数图,不依赖重复值只出现两次,因此也适用于题目允许的多次重复。