【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
}