287. 寻找重复数
一句话套路值当下一跳构成链表 → Floyd 找环入口
题目描述
给定一个包含 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 <= 105nums.length == n + 11 <= nums[i] <= nnums中 只有一个整数 出现 两次或多次 ,其余整数均只出现 一次
进阶:
- 如何证明
nums中至少存在一个重复的数字? - 你可以设计一个线性级时间复杂度
O(n)的解决方案吗?
思路
时间
O(n)、空间 O(1)(最优)空间
O(1)(最优)约束
不能修改数组、只能用 O(1) 额外空间 —— 排序/哈希/set 全部出局。
思路 A(Floyd 判圈)
把下标当结点、nums[i] 当「下一条边」,n+1 个数落在 [1,n],所以一定有环;重复的数就是环的入口。
快慢指针
slow=nums[slow],fast=nums[nums[fast]];
相遇后把一个放回起点,各走一步,再相遇处即入口(Q142 同款)。
思路 B(值域二分)
对值 mid 统计「<= mid 的元素个数」,个数 > mid 说明重复值在左半边。
O(n log n),不需要修改数组,也很好想。
思路 C(原地取负)
把 nums[x] 位置的数取负当 visited —— 但违反「不修改数组」。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0287 {
class Solution {
public:
static int findDuplicate(vector<int>& nums) {
int slow = nums[0], fast = nums[nums[0]];
while (slow != fast) { // 阶段一:找相遇点
slow = nums[slow];
fast = nums[nums[fast]];
}
slow = 0; // 阶段二:一个回起点,同速前进(Q142 的结论)
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
// 值域二分版:不依赖「慢指针能到起点」这个性质,思路更直白
static int findDuplicateBinary(vector<int>& nums) {
int lo = 1, hi = (int)nums.size() - 1; // 值域是 [1, n]
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int cnt = 0;
for (int x : nums)
if (x <= mid) ++cnt; // 统计 <= mid 的元素个数
if (cnt > mid)
hi = mid; // 抽屉原理:重复值在 [lo, mid]
else
lo = mid + 1;
}
return lo;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0287::Solution s;
vector<int> a{1, 3, 4, 2, 2};
CHECK_EQ(s.findDuplicate(a), 2);
CHECK_EQ(s.findDuplicateBinary(a), 2);
vector<int> b{3, 1, 3, 4, 2};
CHECK_EQ(s.findDuplicate(b), 3);
CHECK_EQ(s.findDuplicateBinary(b), 3);
vector<int> c{1, 1};
CHECK_EQ(s.findDuplicate(c), 1);
CHECK_EQ(s.findDuplicateBinary(c), 1);
vector<int> d{2, 2, 2, 2, 2}; // 只有一种数且重复多次
CHECK_EQ(s.findDuplicate(d), 2);
CHECK_EQ(s.findDuplicateBinary(d), 2);
vector<int> e{1, 4, 4, 2, 3}; // 长度为 n+1 时元素必须落在 [1,n](否则下面的快指针会越界)
CHECK_EQ(s.findDuplicate(e), 4);
CHECK_EQ(s.findDuplicateBinary(e), 4);
vector<int> f{1, 2, 3, 4, 5, 6, 6}; // 6 出现两次
CHECK_EQ(s.findDuplicate(f), 6);
CHECK_EQ(s.findDuplicateBinary(f), 6);
// 两版必须完全一致(Floyd 依赖「从 0 出发进环」,二分版不依赖)
vector<int> g{4, 1, 8, 8, 7, 5, 2, 6, 3};
CHECK_EQ(s.findDuplicate(g), s.findDuplicateBinary(g));