友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
287. 寻找重复数
给定一个包含 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 <= 105 -
nums.length == n + 1 -
1 <= nums[i] <= n -
nums中 只有一个整数 出现 两次或多次，其余整数均只出现 一次
进阶：
-
如何证明
nums中至少存在一个重复的数字? -
你可以设计一个线性级时间复杂度 \(O(n)\) 的解决方案吗？
思路分析
题目要求“不能修改数组”和“O(1)的空间复杂度”，就比较难办了。可以利用 142. 环形链表 II中 龟兔赛跑找环的思路来解决：
|
这里应该有一副这样的图片： 
这张图也不够完美，没有把计算公式写出来。 |
如果抛开题目要求的“不能修改数组”和“O(1)的空间复杂度”要求，有更多解法：
-
不考虑空间复杂度，可以用
Set来求解 -
如果可以修改数组，则原地交换（把
nums[i]挪到nums[nums[i]]上）。
| 上图就是 Cyclic Sort 循环排序。 |
-
一刷
-
二刷
-
三刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Find the Duplicate Number.
* Memory Usage: 42.8 MB, less than 5.09% of Java online submissions for Find the Duplicate Number.
*
* Copy from: https://leetcode.com/problems/find-the-duplicate-number/solution/[Find the Duplicate Number - LeetCode]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-05 22:52
*/
public int findDuplicate(int[] nums) {
int tortoise = nums[0];
int hare = nums[0];
do {
tortoise = nums[tortoise];
hare = nums[nums[hare]];
} while (tortoise != hare);
int pointer1 = nums[0];
int pointer2 = hare;
while (pointer1 != pointer2) {
pointer1 = nums[pointer1];
pointer2 = nums[pointer2];
}
return pointer1;
}
/**
* Runtime: 95 ms, faster than 5.83% of Java online submissions for Find the Duplicate Number.
*
* Memory Usage: 37.8 MB, less than 37.29% of Java online submissions for Find the Duplicate Number.
*/
public int findDuplicateBruteForce(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] == nums[j]) {
return nums[i];
}
}
}
return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-13 22:05:18
*/
public int findDuplicate(int[] nums) {
int slow = 0;
int fast = 0;
do {
slow = nums[slow];
fast = nums[fast];
fast = nums[fast];
} while(slow != fast);
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-10-17 21:53:03
*/
public int findDuplicate(int[] nums) {
// 利用快慢指针判断链表是否有环的思路，找到快慢指针的汇合点
int slow = 0, fast = 0;
do {
slow = nums[slow];
fast = nums[fast];
fast = nums[fast];
} while (slow != fast);
// 从链表头开始遍历，直到相遇，则就是重复元素
fast = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}