友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
287. Find the Duplicate Number
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Input: [1,3,4,2,2]
Output: 2Input: [3,1,3,4,2]
Output: 3Note:
-
You must not modify the array (assume the array is read only).
-
You must use only constant, \(O\left(1\right)\) extra space.
-
Your runtime complexity should be less than \(O\left(n^{2}\right)\).
-
There is only one duplicate number in the array, but it could be repeated more than once.
可以使用 142. Linked List Cycle II 中的 Floyd’s Tortoise and Hare (Cycle Detection) 算法来解决。
思路分析
题目要求“不能修改数组”和“O(1)的空间复杂度”，就比较难办了。可以利用龟兔赛跑找环的方式来解决：
如果抛开题目要求的“不能修改数组”和“O(1)的空间复杂度”要求，有更多解法：
-
不考虑空间复杂度，可以用
Set来求解 -
如果可以修改数组，则原地交换（把
nums[i]挪到nums[nums[i]]上）。
-
一刷
-
二刷
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;
}
参考资料
-
Find the Duplicate Number solution - LeetCode 中 Approach #3 Floyd’s Tortoise and Hare (Cycle Detection) [Accepted^] 的好精巧！类似于在链表中发现环。还需要再仔细思考一下这个问题！