给定一个包含 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
50 -> 1
1 -> 3
2 -> 4
3 -> 2
4 -> 2
形成的图如下所示:
从2处形成了环,而且入口就是2。
对于示例2:1
2
3
4
50 -> 3
1 -> 1
2 -> 3
3 -> 4
4 -> 2
形成的图如下所示:
其中环的入口是3,也就是重复的元素。
我们可以看到,在示例2中的图中,1被单独拎出来,指向了它自己,按理说,这也是环啊,怎么说环的入口是3呢?
妙就妙在这里,我们可以看到,所有形成环的链,都是以0开头,而我们从0开始遍历时,根本不会遍历到1,所以1即便是形成了对自己的环,这里也不影响。
这样,就转换成了有一个链表存在环,如何找到入环点的问题,也即 Floyd判环算法。
这个算法分两步,一步是确定有环,使用快慢指针。第二步是找到入环点,快慢指针相遇后,直接将其中一个指针移到起点,然后两个指针同时移动,相遇时就是入环点。
1 | func findDuplicate(nums []int) int { |
这个方法实在是巧妙,正好利用了题目中给的两个已知条件,长度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 | func findDuplicate(nums []int) int { |
整体复杂度为 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 | func findDuplicate(nums []int) int { |