【LeetCode每日一题】287. 寻找重复数.md

287.寻找重复数

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

示例 1:
输入:nums = [1,3,4,2,2]
输出:2
示例 2:
输入:nums = [3,1,3,4,2]
输出:3
示例 3:
输入:nums = [1,1]
输出:1
示例 4:
输入:nums = [1,1,2]
输出:1

提示:

  • 2 <= n <= 3 * 104
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums 中 只有一个整数 出现 两次或多次 ,其余整数均只出现 一次

进阶:
1.如何证明 nums 中至少存在一个重复的数字?
2.你可以在不修改数组 nums 的情况下解决这个问题吗?
3.你可以只用常量级 O(1) 的额外空间解决这个问题吗?
4.你可以设计一个时间复杂度小于 O(n^2) 的解决方案吗?

这个题目,最容易想到的,就是使用哈希表,依次遍历每个元素,使用哈希表将元素缓存起来,遇到重复的直接返回。时间复杂度为O(n),空间复杂度也为O(n)。

但题目中的进阶部分,给出了很多限制,而且,如果使用哈希表的话,其实题目中给出的条件:数组长度 n+1,元素范围[1,n],其实也就没必要了。

既然给出了限制,那么肯定要考虑给出的这两个条件。实在是没想到在这限定下,该如何解,索性看看看官方题解吧。尼玛,官方给出了三种思路,我一个也没想到,这篇博文就记录一下整个学习过程吧。

快慢指针法

我们对nums[]数组建图,每个位置i连一条 i->nums[i]的边。由于存在重复的数字target,因此target这个位置一定有起码两条指向它的边,因此整张图一定存在环,且我们要找的target就是这个环的入口。
这个是官方给出方案中的解题思路,经过苦思冥想,终于明白了。

我们先把每个 i->nums[i] 的边给列出来:
比如,示例一的数组:

1
2
3
4
5
0 -> 1
1 -> 3
2 -> 4
3 -> 2
4 -> 2

形成的图如下所示:

从2处形成了环,而且入口就是2。

对于示例2:

1
2
3
4
5
0 -> 3
1 -> 1
2 -> 3
3 -> 4
4 -> 2

形成的图如下所示:

其中环的入口是3,也就是重复的元素。
我们可以看到,在示例2中的图中,1被单独拎出来,指向了它自己,按理说,这也是环啊,怎么说环的入口是3呢?
妙就妙在这里,我们可以看到,所有形成环的链,都是以0开头,而我们从0开始遍历时,根本不会遍历到1,所以1即便是形成了对自己的环,这里也不影响。

这样,就转换成了有一个链表存在环,如何找到入环点的问题,也即 Floyd判环算法
这个算法分两步,一步是确定有环,使用快慢指针。第二步是找到入环点,快慢指针相遇后,直接将其中一个指针移到起点,然后两个指针同时移动,相遇时就是入环点。

1
2
3
4
5
6
7
8
9
10
11
func findDuplicate(nums []int) int {
slow, fast := 0, 0
for slow, fast = nums[slow], nums[nums[fast]]; slow != fast; slow, fast = nums[slow], nums[nums[fast]] {
}
slow = 0
for slow != fast {
slow = nums[slow]
fast = nums[fast]
}
return slow
}

这个方法实在是巧妙,正好利用了题目中给的两个已知条件,长度n+1,元素范围[1,n],这样元素与索引正好处于同一个范围(除了0,但也正是因为0,才有了开头),巧妙的将数组转换成链表思想。

二分查找

我们定义cnt[i]表示nums中小于等于i的数有多少个,以示例1为例,[1,3,4,2,2],得到如下表格:

我们发现,对于[1,target-1]区间里所有的数,cnt[i] <= i,而对于 [target, n]里所有的数, cnt[i]>i,而且cnt具有单调性,所以,我们可以使用二分查找的方式来找到重复的数字。
这里比较巧妙的一点是,我们不需要事先算出cnt的所有值(如果要算出所有值,时间复杂度为O(n^2)),而是直接对cnt进行二分,拿到对应的cnt后,再回数组去统计num的个数进行对比。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func findDuplicate(nums []int) int {
n := len(nums)
l, r := 1, n - 1
ans := -1
for l <= r {
mid := (l + r) >> 1
cnt := 0
for i := 0; i < n; i++ {
if nums[i] <= mid {
cnt++
}
}
if cnt <= mid {
l = mid + 1
} else {
r = mid - 1
ans = mid
}
}
return ans
}

整体复杂度为 O(nlogn),二分查找cnt复杂度为O(logn),回数组统计num个数复杂度为O(n),因此整体复杂度为O(nlogn)。

二进制位运算

我们将数组中每个元素按二进制形式展开,形成如上表格,其中[1,2,3,4,1]即为数组中每个元素,x为所有元素对应位上1的个数,y为[1,n]所有元素对应位上1的个数。最后一列,如果x>y,那么取1,否则取0,形成的这个二进制数,就是重复的数。

这个方法的逻辑点在哪呢?刚看的时候,也是很蒙。所以我把官方的例子稍微改了一下,用了上面这个例子,数组为[1,2,3,4,1]来做示例。

试想一下,如果说在一个长度为 n+1 的数组上,每个元素的范围是 [1,n],并且如果只有一个元素重复,那么该如何确定重复的元素呢?
如果加上只有一个元素重复,那么我们可以直接用sum(nums)-sum([1,n])得到重复数字。上面这个逻辑就是用的这个原理,只不过是由于可能有多个重复元素,我们无法直接用sum(nums)-sum([1,n])来获得重复数字,我们将数字二进制形式展开,这样我们每一位上的x-y必然大于等于0,大于0的,说明是重复数字相应的位上重复了,即使重复数字有多个,我们得到相应二进制位上x-y的值就是重复的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func findDuplicate(nums []int) int {
n := len(nums)
ans := 0
bit_max := 31
for ((n - 1) >> bit_max) == 0 {
bit_max--
}
for bit := 0; bit <= bit_max; bit++ {
x, y := 0, 0
for i := 0; i < n; i++ {
if (nums[i] & (1 << bit)) > 0 {
x++
}
if i >= 1 && (i&(1<<bit)) > 0 {
y++
}
}
if x > y {
ans |= 1 << bit
}
}
return ans
}