力扣287——寻找重复数

这道题主要就是找规律,基于之前142题环形链表II的规律,就能解决了。

原题

给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。

示例 1:

1
2
输入: [1,3,4,2,2]
输出: 2

示例 2:

1
2
输入: [3,1,3,4,2]
输出: 3

说明:

  • 不能更改原数组(假设数组是只读的)。
  • 只能使用额外的 O(1) 的空间。
  • 时间复杂度小于 O(n2) 。
  • 数组中只有一个重复的数字,但它可能不止重复出现一次。

原题url:https://leetcode-cn.com/problems/find-the-duplicate-number/

解题

普通思路

针对说明里的前两条,其实就分别对应了解题的两种思路:

  1. 先原地排序,再遍历寻找。
  2. 使用集合记录已经出现过的数字。

当然了,既然已经在说明里被禁止了, 那么就应该想想别的思路了。

我还想到了利用 bitMap 的思路,相当于用一个数字的二进制,各个位上是否为1来表示该数字是否出现过。但考虑到 java 里 int 的最大值是 (2^31 - 1),long 的最大值也不过是(2^63 - 1),那都是要求 n 不能大于100的。因此,这种思路也是暂时不可取的。

抽象为环形链表II

如果将数组的下标和值抽象成链表的话,出现重复数字也就意味着出现链表中有环,那么这道题就是之前做到的力扣142——环形链表II一模一样了。

我们举例说明一下,假设数组是[1, 5, 7, 3, 2, 4, 6, 7],那么将其转化成的链表就是:0 -> 1 -> 5 -> 7 -> 3 -> 2 -> 4 -> 6 -> 7 ....无限循环。

那我们就可以借助快慢指针:

  1. 快指针一次走两步,慢指针一次走一步,直到他们相遇;
  2. 快指针再次从起点出发,但此时两个指针都是一次走一步;
  3. 当他们再次相遇后,相遇点就是重复的整数。

接下来让我们看看代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int findDuplicate(int[] nums) {
// 参考环形链表II,利用快慢指针
// 快指针一次走两步,慢指针一次走一步,当他们相遇后
// 快指针再次从起点出发,但此时两个指针都是一次走一步
// 当他们再次相遇后,相遇点就是重复的整数

int slow = nums[0];
int fast = nums[nums[0]];
while (slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}

fast = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}

return fast;
}
}

提交OK,时间复杂度为:O(n),空间复杂度是:O(1)。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题目主要还是在于寻找其中的规律,转化为环形链表来思考。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。

https://death00.github.io/

公众号:健程之道

健健 wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
如果您感觉文章不错,也愿意支持一下作者的话