LeetCode 287 寻找重复数

2021-01-28 2021-01-28 约 2016 字预计阅读 5 分钟

本题是一道反常规的题目，平时不会照样使用本文的方法解决类似问题，但是文中所用的位运算和双指针方法却十分巧妙，值得细究。同时，构建二分解法时需要对常见的二分法代码进行合理调整，如果死记硬背模板代码则不仅难以构建解法也会出现各种边界问题。故本题也不失为一道优秀的二分法试题。

题目描述

原题链接如下： LeetCode 287 寻找重复数

题目大意

一个数组 nums 的内容都是 1 到 n 的范围内的整数，只要一个数字出现次数大于两次，解法限制如下：

不可改变原有数据
空间复杂度必须为 $O(1)$
时间复杂度小于 $O(n^{2})$

输入与输出

示例输入为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Input 1:
nums = [1,3,4,2,2]

Input 2:
nums = [3,1,3,4,2]

Input 3:
nums = [1,1]

Input 4:
nums = [1,1,2]

其中，数据各有如下取值范围：

$2 \le n \le 30000$
nums 的长度为 n + 1
$1 \le num \le n\ (\forall num \in nums)$

对应输出为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Output 1:
2

Output 2:
3

Output 3:
1

Output 4:
1

解题思路

首先要明白，工作中一般会直接使用哈希表进行去重判断。但是本题对空间复杂度的限制使得此解法不可实现，同时不准修改原数据又否决了排序的可能性，可能要使用一些“时间换空间的办法”来应对。

解法一：二分法

我们可以根据抽屉原理推断：假设在原数组内任选一个数字 x，那么原数组可以被如此划分：

1
[1, x) + { 可能有 m 个 x，m > 0 } + (x, n]

不难看出，nums 在 [1, x) 内的元素数量必定为 x - 1，而 [1, x] 内的元素数量则不可直接确定，可以假设为 y，y 与 x 的关系如下：

如果 x 不是重复元素，则 $x = y$
如果 x 就是重复元素，则 $x < y$

换句话说，只要归于这个任取的 x，只要 nums 内不大于它的元素数量 y 和它本身满足 $x \le y$，则重复元素必定在 [1, x] 之内。

如此，我们自然可以想到使用二分法解决本题，因为我们要不断的抛弃右边的区间 (mid, right]，故二分法的循环条件为 left < right；而且需要保证答案在 [left, mid] 之内，故抛弃右半区间后 right 要更新为 mid，而非常见的 mid - 1。

本解法需要在每次二分的时候，遍历 nums 元素，因而时间复杂度为 $O(n\log{n})$

解法二：位运算

如果 n 已知，那么 [1, n] 的所有整数是确定的，则这些数字转换为二进制后在同一位上的 1 的总数是确定不变的。一旦我们新加入了一个重复数字 x，那么重复数字的所有为 1 的位置上 1 的总数就会加一。那么我们不妨假设任意位置上 nums 中的二进制 1 的总数为 $c_{1}$，正常的 [1, n] 范围的整数的二进制 1 的总数为 $c_{2}$。此时，我们只需统计 nums 中所有数字在每个二进制位，只要 $c_{1} > c_{2}$ 则 x 在此位置为 1，否则为 0。

可是，如果 nums 中重复的数字多余两个，那么 [1, n] 中原先的数字就会被 x 取代。那么，考虑任一被 x 替换的元素 t 的任一二进制位我们可以分情况讨论得出如下结论：

t	x	$c_{1}$ 变化	$c_{1} > c_{2}$
0	0	不变	false
0	1	加一	true
1	0	减一	false
1	1	不变	true

可以看出，原有结论仍然成立，那么我们就能得到相应的算法。本算法需要在 n 的每个二进制位上都进行一次 nums 的遍历统计，同时统计 [1, n] 范围数字对应的 1 的数量，所以总时间复杂度为 $O(n\log{n})$

解法三：双指针

本题的 nums 内部元素取值都在其下标的范围，那么我们其实可以认为它是一种特殊的链表：

数组的下标是链表节点的地址指针
数组的头节点指针是 0
数组内的元素则是链表节点内的 next 指针
此时，“链表”的节点内不保存数据（当然也可认为数据和 next 指针相同）

显然，如果从头节点开始的链表，数组的特殊性质导致了这个链表不可能存在尾部元素，即每次遍历一个节点它的 next 指针对应的数组元素必定合法，而且内部必定有值指向链表的节点，链表遍历无尽头但是数组元素有限，即环必然出现。因为某些节点的 next 指针存在重复，导致环的出现，而且重复的元素就是环的入口。

**注意：**严格来看，本题的元素应该当作图来处理。

根据 Floyd 判圈算法，使用快慢双指针，快指针移动距离为满指针的两倍，那么两个指针必定在环内相遇。假设环的周长是 L，从头节点到环的入口需要 a 步，从环入口到两指针相遇点需 b 步，从相遇点继续向前回到环入口需 c 步，那么必定有：

$$b + c = L$$

而且，根据我们对两个指针的定义，满指针走了 a + b 步，快指针走了满指针的两倍路程，故：

$$ 2(a + b) = a + b + k \cdot L \ (k > 0) $$

那么，可以得出如下等式：

$$ \begin{aligned} a &= k \cdot L - b \\ &= (k - 1) \cdot L + L - b \\ &= (k - 1) \cdot L + c \end{aligned} $$

即在快慢指针相遇之后，把慢指针再赋值为头节点然后开始和快指针一同样的速度运动，那么它们必定再环的入口相遇（因为此时慢指针重新走了 a 步）。本算法的核心部分是 Floyd 判圈算法，其时间复杂度为 $O(n)$，而剩余代码指针运动步数不会超过 n，所以总的时间复杂度不会增加。

代码

二分法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    fun findDuplicate(nums: IntArray): Int {
        var left = 1
        var right = nums.size - 1
        while (left < right) {
            val mid = (left + right) / 2
            val count = nums.count { it <= mid }
            if (count > mid) right = mid
            else left = mid + 1
        }
        return left
    }
}

位运算：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    fun findDuplicate(nums: IntArray): Int {
        val n = nums.lastIndex
        var bitLen = 0
        var re = 0
        while ((n shr bitLen) != 0) bitLen++
        val range = 1..n
        for (i in 0 until bitLen) {
            val tmp = 1 shl i
            val cnt1 = nums.count { it and tmp != 0 }
            val cnt2 = range.count { it and tmp != 0 }
            if (cnt1 > cnt2) re = re or tmp
        }
        return re
    }
}

双指针：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    fun findDuplicate(nums: IntArray): Int {
        var slow = 0
        var fast = 0
        do {
            slow = nums[slow]
            fast = nums[nums[fast]]
        } while (slow != fast)
        slow = 0
        while (slow != fast) {
            slow = nums[slow]
            fast = nums[fast]
        }
        return slow
    }
}

目录