题目描述

[牛客网]

03. 数组中重复的数字

在一个长度为 n 的数组里的所有数字都在 0n - 1 的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的,也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为 7 的数组 {2, 3, 1, 0, 2, 5, 3},那么对应的输出是第一个重复的数字 2

解法 1:哈希表

首先明确什么是「第一个重复的数字」,可以有两种理解,分别是第一次发生重复的数字(记为 A),或者重复的数字中的第一个(记为 B)。举个简单的例子,假如待操作的数组为 [0, 1, 2, 3, 2, 1],那么 A 应该是 2,而 B 应该是 1。这里我们都遵从 A 设定,以下的解法同。

顺序扫描一遍,每个数存入一个哈希表,如果遇到该数已在哈希表则返回。

如果数组长度为 $n$,那么

  • 时间复杂度为 $O(n)$,需要一次遍历
  • 空间复杂度为 $O(n)$,需要一个哈希表。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    # 要求:
    # 1. 将第一个重复的数字赋值到 duplication[0]。
    # 2. 函数返回 True / False。
    def duplicate(self, numbers, duplication):
        visited = set()
        for n in numbers:
            if n in visited:
                duplication[0] = n
                return True
            visited.add(n)
        return False
  • 运行时间:25ms
  • 占用内存:5624k

解法 2:标记索引为当前值的桶

基于哈希表的方法需要 $O(n)$ 空间复杂度,我们思考能不能优化到 $O(1)$ 复杂度。观察题目中给出的两个条件:

  1. 数组长度为 n;
  2. 数字的范围都在 0 到 n - 1。

这也意味着如果数组中不存在数字重复,那么 0 到 n -1 范围内,每个索引只对应一个唯一的数字。那么我们可以通过遍历一遍原数组,假设遍历索引为 i 的数字 nums[i],那么我们只需要标记索引为 nums[i] 的桶,那么当我们遇到重复的数字时,就会发现已经标记过了,得解。

这里的标记方式可以有很多种,比如说:

  1. 将索引为 i 的数字与索引为 nums[i] 的数字交换,交换之后索引为 nums[i] 的数字的值也是 nums[i]
  2. 将索引为 nums[i] 的数字转为相反数(以下采用这种做法)。
  3. 将索引为 nums[i] 的数字加上 n
  4. 将索引为 nums[i] 的数字减去 n

如果数组长度为 $n$,那么

  • 时间复杂度为 $O(n)$,需要一次遍历
  • 空间复杂度为 $O(1)$,直接在原数组上做了标记。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    # 要求:
    # 1. 将第一个重复的数字赋值到 duplication[0]。
    # 2. 函数返回 True / False。
    def duplicate(self, numbers, duplication):
        for n in numbers:
            if numbers[abs(n)] < 0:
                duplication[0] = abs(n)
                return True
            numbers[n] *= -1
        return False
  • 运行时间:35ms
  • 占用内存:5708k

解法 3:二分查找法

这个解法出自《剑指 Offer》原书,比较巧妙,但是存在很大缺陷。其基于抽屉原理:将 n + 1 个苹果放入 n 个抽屉必定至少有一个抽屉拥有超过 1 个苹果,具体做法是将数值范围 $[0, n]$ 分割成两个区间 $[0, \frac{n}{2}]$、$(\frac{n}{2}, n]$,分别统计在原数组中的数值落在这两个区间的数量,若其中一个数量大于 $\frac{n}{2}$,那么该区间内有数字发生重复,然后再次执行二分查找。这个算法的时间复杂度为 $n \log n$(查找 $O(\log n)$ 次,每次 $O(n)$ 复杂度),空间复杂度 $O(1)$。

但是这个方法有 2 个缺陷:

  1. 该算法无法找到特定场景下的数字,例如找不到 [0, 1, 2, 2] 里面的 2
  2. 该算法找到的重复的数字不能保证是第一个重复的数字。

代码略。