0287. Find the Duplicate Number¶
题目信息¶
- 题号:
0287
- 难度:
Medium
- 主题:
数组、重复值、只读输入、常数空间
- 原题:
- 重点:
长度为
n+1而取值只有1..n、唯一重复值可出现多次、不能修改数组
题目重述¶
给定包含 n+1 个整数的数组 nums,每个元素都位于 [1, n]。题目保证只有一个不同的整数在数组中重复出现,但这个整数可能出现两次,也可能出现更多次。返回这个唯一的重复值。
1 <= n <= 10^5。答案值唯一,不要求返回重复位置或出现次数。必须把输入数组视为只读,不能通过排序、取负标记或交换元素来改变其内容;同时只允许使用常数级额外空间。题目的进阶要求整体运行时间不超过 O(n)。
自建示例¶
重复值出现两次:
输入:nums = [2, 5, 1, 4, 3, 5]
输出:5
解释:数组长度为 6,因此 n = 5,所有值都在 1..5 中;只有 5 重复出现。
同一个值出现多次:
输入: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++ 实现¶
class Solution {
public:
int findDuplicate(std::vector<int>& 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)。
算法依赖的是值域和长度形成的函数图,不依赖重复值只出现两次,因此也适用于题目允许的多次重复。