#P4103. 寻找重复数
-
ID: 2340
Tried: 168
Accepted: 60
Difficulty: 5
寻找重复数
题目描述
给定一个包含 n+1 个整数的数组 nums，其数字都在 [1,n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数，返回 这个重复的数。
你的解决方案必须 不修改 数组 nums，且只用常量级 O(1) 的额外空间。
输入描述
- 第一行输入一个整数
n（1≤n≤105），表示nums的长度为 n+1。 - 第二行输入
n + 1个整数，表示数组nums。
输出描述
输出 nums 中唯一的重复整数。
输入示例
4
1 3 4 2 2
输出示例
2
提示
nums的长度始终为n + 1。nums中的所有数字都在[1, n]范围内。nums中 只有一个整数出现两次或多次，其余整数均只出现一次。
1. 问题回顾与约束
- 数组长度为 n+1，元素都在 [1,n] 的范围内。
- 因「鸽巢原理」，必存在至少一个值出现两次或以上。
- 要求：
- 不能 修改输入数组；
- 只允许 O(1) 额外空间；
- 时间复杂度 O(n)。
常见但不满足约束的方法有：
- 排序后扫描（破坏原数组）；
- 哈希表或布尔标记（需要 O(n) 空间）；
- 位运算统计每一位（可以不用修改数组，但实现较复杂且常数项大）；
- 值域二分（O(nlogn) 时间）。
Floyd 判圈算法，恰好满足全部要求，且思路优雅。
2. 为什么能“造出”环？
把数组看成一个「从下标到下标」的映射函数：
f(i)=nums[i]注意下标 i 与取值都在 [1,n]，因此：
- 从 0 出发：先访问 f(0)=nums[0]∈[1,n]；
- 再访问 f(f(0))=nums[nums[0]]；
- ……
因为所有访问都落在 1 到 n 的下标上，而一共有 n+1 次访问（如果一直不停），根据鸽巢原理，在下标集合 {1,2,…,n} 中必有重复访问，也即在这个「链表」上存在一个环。
- 链头：下标 0
- 链身：下标 1…n，不断跳转
- 环：从某个「入口」点开始，不断指向自己或之前访问过的点
而环的入口对应的正是那个重复出现的数：
因为如果数 x 被重复出现，那么在映射中就会出现两条不同的路径都指向下标 x，从而形成环的入口。
3. Floyd 判圈法分两步走
3.1 第一步：找相遇点（证明在环内）
- 设两个指针
slow、fast，都从 nums[0] 开始。 - 每次
slow = f(slow)走一步，fast = f(f(fast)))走两步。 - 如果存在环，快指针一定会在环内追上慢指针。
初始化：
slow = f(0) = nums[0]
fast = f(0) = nums[0]
循环直到相遇：
slow = f(slow)
fast = f(f(fast))
if slow == fast: break
- 最多经过 O(n) 步就能相遇。
3.2 第二步：找环的入口（就是重复的数）
- 相遇后，
slow（或fast）停在环内的某个位置； - 新建指针
ptr1指向 起点nums[0]，ptr2指向相遇点slow； - 此后，两指针都 每次走一步，最终它们会在 环入口 相遇。
ptr1 = nums[0]
ptr2 = slow
while ptr1 != ptr2:
ptr1 = f(ptr1)
ptr2 = f(ptr2)
返回 ptr1 // 入口下标，即重复的数
为什么能准定位入口？
经典数学推导可参考《算法导论》中对环检测的分析，结论是：
- 设链头到入口距离为 a，
- 环长度为 λ，
- 快慢指针在环内相遇时，慢指针已走 a+b 步（其中 b 是从入口再走到相遇点的距离），快指针走了 a+b+kλ 步（快指针比慢指针多绕了 k 圈）。
- 快慢指针速度比 2:1，可得 2(a+b)=a+b+kλ⟹a+b=kλ。
- 则 a=kλ−b，也就是从相遇点再走 a 步，恰好回到入口。
因此，一根从头出发、一根从相遇点出发、同速前进，最终必在入口相遇。
4. 详细示例演示
以 nums = [3, 1, 3, 4, 2]（长度 5，取值 1…4）为例。
-
构造映射
下标 : 0 → 1 → 3 → 4 → 2 → 3 → … 对应值: nums[0]=3 → nums[3]=4 → nums[4]=2 → nums[2]=3 → …从 0 出发，很快进入了环：3→4→2→3…
-
第一步：找相遇点
slow 路径：0→3→2→3→2→… fast 路径：0→3→2→2→2→… 相遇位置：下标 2（nums[2]=3） -
第二步：找入口
ptr1 从头：0→3→4→2→3… ptr2 从相遇：2→3→4→2→… 它们在「下标 3」相遇，对应的数值是 3因此答案是 3，正是数组中唯一重复的那个数。
代码实现
Python
def findDuplicate(nums):
# 第一次相遇：找环内相遇点
slow = nums[0]
fast = nums[0]
while True:
slow = nums[slow] # 慢指针走一步
fast = nums[nums[fast]] # 快指针走两步
if slow == fast:
break
# 第二次相遇：找环的入口
ptr1 = nums[0]
ptr2 = slow
while ptr1 != ptr2:
ptr1 = nums[ptr1]
ptr2 = nums[ptr2]
return ptr1
# 读取输入并输出结果
if __name__ == "__main__":
n = int(input().strip())
nums = list(map(int, input().split()))
print(findDuplicate(nums))
Java
import java.util.Scanner;
public class Main {
// 寻找重复数
public static int findDuplicate(int[] nums) {
// 第一次相遇：找环内相遇点
int slow = nums[0];
int fast = nums[0];
do {
slow = nums[slow]; // 慢指针走一步
fast = nums[nums[fast]]; // 快指针走两步
} while (slow != fast);
// 第二次相遇：找环的入口
int ptr1 = nums[0];
int ptr2 = slow;
while (ptr1 != ptr2) {
ptr1 = nums[ptr1];
ptr2 = nums[ptr2];
}
return ptr1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
nums[i] = sc.nextInt();
}
System.out.println(findDuplicate(nums));
sc.close();
}
}
C++
#include <bits/stdc++.h>
using namespace std;
// 寻找重复数（Floyd 判圈法）
int findDuplicate(const vector<int>& nums) {
// 第一次相遇：找环内相遇点
int slow = nums[0];
int fast = nums[0];
do {
slow = nums[slow]; // 慢指针走一步
fast = nums[nums[fast]]; // 快指针走两步
} while (slow != fast);
// 第二次相遇：找环的入口
int ptr1 = nums[0];
int ptr2 = slow;
while (ptr1 != ptr2) {
ptr1 = nums[ptr1];
ptr2 = nums[ptr2];
}
return ptr1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> nums(n + 1);
for (int i = 0; i < n + 1; i++) {
cin >> nums[i];
}
cout << findDuplicate(nums) << "\n";
return 0;
}