剑指Offer 面试题03. 数组中的重复数字（易）& LeetCode 287. 寻找重复数（中）

数组去重问题，如何用空间换时间，以及如何用时间换空间？

原题链接

面试题03. 数组中重复的数字

Question

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1： 

1
2
3
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：2 <= n <= 100000

测试用例

功能测试：长度为n的数组里包含一个或多个重复的数字。 特殊输入：数组中不包含重复的数字；输入空指针；长度为n的数组中包含0～n-1之外的数字）。

本题考点

考查应聘者对一维数组的理解及编程能力。一维数组在内存中占据连续的空间，因此我们可以根据下标定位对应的元素。 考查应聘者分析问题的能力。当应聘者发现问题比较复杂时，能不能通过具体的例子找出其中的规律，是能否解决这个问题的关键所在。

注意LeetCode上的面试题03和《剑指offer》书上的面试题03题目不同

LeetCode上的面试题03：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

《剑指offer》书上的面试题03：在一个长度为 n+1 的数组 nums 里的所有数字都在 1～n 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

基于hash map和一次遍历算法在这两种题目上都能正常解决问题。

Intuition

基于hash map

遍历数组，利用 hash map 建立数值和数值出现次数的关系的映射，一旦发现有出现两次以上的数字，即停止遍历输出即可。

算法

  • 声明 hash map
  • for 循环 nums
    • 如果当前 num 在 hash map 中，就直接 ruturn 当前 num。
    • 否则就将当前 num 加入到 hash map 中。

复杂度分析

时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

一次遍历

我们注意到数组中的数字都在0~n-1的范围内。如果这个数组中没有重复的数字，那么当数组排序之后数字 i 将出现在下标为 i 的位置。由于数组中有重复的数字，有些位置可能存在多个数字，同时有些位置可能没有数字。 现在让我们重排这个数组。从头到尾依次扫描这个数组中的每个数字。

算法

  • 当扫描到下标为 i 的数字时，首先比较这个数字（用 m=nums[i] 表示）是不是等于 i 。
    • 如果是，则接着扫描下一个数字；
    • 如果不是，则再拿它和第 m 个数字进行比较。
      • 如果它和第 m 个数字相等，就找到了一个重复的数字（该数字在下标为i 和 m 的位置都出现了），return 这个找到数字。
      • 如果它和第 m 个数字不相等，就把第 i 个数字和第 m 个数字交换，把 m 放到属于它的位置。
    • 接下来再重复这个比较、交换的过程，直到我们发现一个重复的数字。

复杂度分析

时间复杂度：\(O(n)\)
空间复杂度：\(O(1)\)

Code

基于hash map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# coding: utf-8

from typing import List

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        # 声明hash map
        hash_map = dict()
        # for循环nums
        for num in nums:
            if num in hash_map:
                return num
            else:
                hash_map[num] = 1

if __name__ == "__main__":
    arguments = [[2, 3, 1, 0, 2, 5, 3]]
    answers = [[2, 3]]
    solution = Solution()
    for i in range(len(arguments)):
        result = solution.findRepeatNumber(arguments[i])
        print(result in answers[i])

一次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
            if not nums:  return False
            length = len(nums)
            for i in range(length):
            if nums[i] < 0 or nums[i] > length:
                return False
        for i in range(length):
            while nums[i] != i:
                # 找到重复
                if nums[i] == nums[nums[i]]:
                    return nums[i]
                # 交换nums[i]和nums[nums[i] 数字归位
                tmp = nums[nums[i]]
                nums[nums[i]] = nums[i]
                nums[i] = tmp

        return False

Extension

Question

题目二：不修改数组找出重复的数字。 在一个长度为n+1的数组里的所有数字都在1～n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组 [2, 3, 5, 4, 3, 2, 6, 7]，那么对应的输出是重复的数字2或者3。

Related Question

287. 寻找重复数

Test Case

长度为n的数组里包含一个或多个重复的数字。 数组中不包含重复的数字。 无效输入测试用例（输入空指针）。

Knowledge

考查应聘者对一维数组的理解及编程能力。一维数组在内存中占据连续的空间，因此我们可以根据下标定位对应的元素。 考查应聘者对二分查找算法的理解，并能快速、正确地实现二分查找算法的代码。 考查应聘者的沟通能力。应聘者只有具备良好的沟通能力，才能充分了解面试官的需求，从而有针对性地选择算法解决问题。

Intuition

之前空间复杂度为 \(O(n)\) 的 hash map 方案，一样可以解决这个问题。这里讨论一个空间复杂度为 \(O(1)\) 的新方案。

算法 - 我们把从 1～n 的数字从中间的数字 m 分为两部分，前面一半为 1～m，后面一半为 m+1～n。 - 如果 1~m 的数字的数目超过 m，那么这一半的区间里一定包含重复的数字，设置 end = middle，将 end前移动，在 [start, middle] 区间寻找重复元素； - 否则，另一半 m+1～n 的区间里一定包含重复的数字。设置 start = middle + 1，将 start 后移，在[middle+1, end] 区间内寻找重复元素； - 我们可以继续把包含重复数字的区间一分为二，直到找到一个重复的数字。这个过程和二分查找算法很类似，只是多了一步统计区间里数字的数目。

举例 我们以长度为 8 的数组为 [2, 3, 5, 4, 3, 2, 6, 7] 例分析查找的过程。根据题目要求，这个长度为 8 的所有数字都在1~7的范围内。中间的数字 4 把1~7的范围分为两段，一段是1~4，另一段是5～7。接下来我们统计1~4这4个数字在数组中出现的次数，它们一共出现了5次，因此这4个数字中一定有重复的数字。

接下来我们再把1~4的范围一分为二，一段是1、2两个数字，另一段是3、4两个数字。数字 1 或者 2 在数组中一共出现了两次。我们再统计数字 3 或者 4 在数组中出现的次数，它们一共出现了3次。

这意味着 3、4 两个数字中一定有一个重复了。我们再分别统计这两个数字在数组中出现的次数。接着我们发现数字 3 出现了两次，是一个重复的数字。

复杂度分析 上述代码按照二分查找的思路，如果输入长度为n的数组，那么函数 countRange 将被调用 \(O(logn)\) 次，每次需要 \(O(n)\) 的时间，因此总的时间复杂度是 \(O(nlogn)\)，空间复杂度为 \(O(1)\)。和最前面提到的需要 \(O(n)\) 的辅助空间的算法相比，这种算法相当于以时间换空间。 需要指出的是，这种算法不能保证找出所有重复的数字。例如，该算法不能找出数组 [2, 3, 5, 4, 3, 2, 6, 7] 中重复的数字2。这是因为在 1~2 的范围里有 1 和 2 两个数字，这个范围的数字也出现 2 次，此时我们用该算法不能确定是每个数字各出现一次还是某个数字出现了2次。

总结 从上述分析中我们可以看出，如果面试官提出不同的功能要求（找出任意一个重复的数字、找出所有重复的数字）或者性能要求（时间效率优先、空间效率优先），那么我们最终选取的算法也将不同。这也说明在面试中和面试官交流的重要性，我们一定要在动手写代码之前弄清楚面试官的需求。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def contRange(self, nums, length, start, end):
        if not nums:
            return 0
        count = 0
        for i in range(length):
            if start <= nums[i] <= end:
                count += 1
        return count

    def findDuplicate(self, nums: List[int]) -> int:
        if not nums:  return False
        length = len(nums)
        start = 1  # 剑指offer原题里面数组第一个数字是1，LeetCode题目里面数组第一个数字是0，所以这个改成0。
        end = length - 1
        while start <= end:
            middle = start + (end - start) // 2
            count = self.contRange(nums, length, start, middle)
            if start == end:
                if count > 1:
                    return start
                else:
                    break
            if count > middle - start + 1:
                end = middle
            else:
                start = middle + 1

        return -1

Condition Change

如果将题目从“在一个长度为n+l的数组里的所有数字都在1～n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。”改成“在一个长度为n的数组里的所有数字都在0～n-1的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。”。

可以发现数字范围从1～n变成了0～n-1，则遇到如 [0, 1, 2, 0, 4, 5, 6, 7, 8, 9] 这样的输入，就要对 count == middle - start + 1 进行讨论了。

第一次遍历，start=0，end=9，middle=4，0-4的数字有0，1，2，3，4，出现5次，即count=5，而middle - start + 1=5，此时如果再按照书上的代码，

1
2
3
4
if count > middle - start + 1:
    end = middle
else:
    start = middle + 1

start就会被设置为5，但实际上下一个搜索区间应该是start=0，end=4。因此需要对count == middle - start + 1 进行讨论。start 初始值也要从1改为0。

算法

  • 我们把从 1～n 的数字从中间的数字 m 分为两部分，前面一半为 1～m，后面一半为 m+1～n。
    • 如果 1~m 的数字的数目等于 m，那么就要判断 1~m 的数字是否都在 nums 中。
      • 如果都在其中， m+1～n 的区间里一定包含重复的数字。
      • 否则，1~m 的区间里一定包含重复的数字。
    • 如果 1~m 的数字的数目超过 m，那么这一半的区间里一定包含重复的数字；
    • 否则，另一半 m+1～n 的区间里一定包含重复的数字。
  • 我们可以继续把包含重复数字的区间一分为二，直到找到一个重复的数字。这个过程和二分查找算法很类似，只是多了一步统计区间里数字的数目。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
    def contRange(self, nums, length, start, end):
        if not nums:
            return 0
        count = 0
        for i in range(length):
            if start <= nums[i] <= end:
                count += 1
        return count

    def findRepeatNumber(self, nums: List[int]) -> int:
        if not nums:  return False
        length = len(nums)
        start = 0  # 剑指offer原题里面数组第一个数字是1，LeetCode题目里面数组第一个数字是0，所以这个改成0。
        end = length - 1
        while start <= end:
            middle = start + (end - start) // 2
            count = self.contRange(nums, length, start, middle)
            if start == end:
                if count > 1:
                    return start
                else:
                    break
            # 相等的情况下有两种情况，一是 0, 1, 2, 3 的情况，二是 2, 2, 3, 3
            if count == middle - start + 1:
                flag = True
                for j in range(start, middle+1):
                    if not j in nums:
                        flag = False
                        break
                # 第一种情况就在后面查找 start = middle + 1
                if flag:
                    start = middle + 1
                # 第二种情况就在前面查找 end = middle
                else:
                    end = middle
            elif count > middle - start + 1:  # 注意，这里是 >
                end = middle
            else:
                start = middle + 1

        return -1

时间复杂度 \(O(nlogn)\) 。
空间复杂度 \(O(1)\)