[剑指 Offer 第 2 版第 3 题] “数组中重复的数字”做题记录

第 3 题：数组中重复的数字（桶排序，抽屉原理）

传送门：AcWing：数组中重复的数字，牛客网 online judge 地址。

给定一个长度为 $n$ 的整数数组 nums，数组中所有的数字都在 $0\simn-1$ 的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意：如果某些数字不在 $0\simn-1$ 的范围内，或数组中不包含重复数字，则返回 $-1$ ；

样例：

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 $2$ 或 $3$ 。

思路1：最容易想到用哈希表判重。在 $n$ 不超过 $32$ 的时候，使用位运算可以实现 $O(1)$ 空间复杂度判重。

思路2：排序以后，再遍历一遍就知道哪个重复了。

思路3：“抽屉原理”。这道题实际上是要求我们使用桶排序的思想（一个萝卜一个坑），找出重复的数字。

Python 代码：这个解法会修改原始数组

  class Solution(object):
        def duplicateInArray(self, nums):
            """
            :type nums: List[int]
            :rtype int
            """

            size = len(nums)
            if size < 2:
                return -1

            # 先统一检查数字是不是越界了
            for i in range(size):
                if nums[i] < 0 or nums[i] > size - 1:
                    return -1

            for i in range(size):

                # nums[i] 应该在 i 的位置上
                while i != nums[i]:
                    # 发现要交换的那个数和自己一样，就可以返回了
                    if nums[i] == nums[nums[i]]:
                        return nums[i]
                    self.__swap(nums, i, nums[i])
            return -1

        def __swap(self, nums, index1, index2):
            if index1 == index2:
                return
            temp = nums[index1]
            nums[index1] = nums[index2]
            nums[index2] = temp

思路4：下面的问题可以不修改数组找出重复的数字，即使用“二分法”。

LeetCode 第 287 题：寻找重复数

传送门：287. 寻找重复数。

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2] 输出: 2

示例 2:

输入: [3,1,3,4,2] 输出: 3

说明：

不能更改原数组（假设数组是只读的）。

只能使用额外的 $O(1)$ 的空间。

时间复杂度小于 $O(n^2)$ 。

数组中只有一个重复的数字，但它可能不止重复出现一次。

思路：分治法，用二分去做，是对“数”做二分，而不是对“索引”做二分。

Python 代码：使用了二分法的模板，要定位的“数”根据题意在 $1$ 和 $n$ 之间

  class Solution:

        def findDuplicate(self, nums):
            """
            【不修改数组找出重复的数字】
            给定一个包含 n + 1 个整数的数组 nums，
            其数字都在 1 到 n 之间（包括 1 和 n），
            可知至少存在一个重复的整数。
            假设只有一个重复的整数，找出这个重复的数。
            :type nums: List[int]
            :rtype: int
            """
            left = 1
            right = len(nums) - 1
            while left < right:
                # 取中点有两种方式，偏左和偏右
                mid = left + (right - left + 1) // 2  # 4
                count = 0
                for num in nums:
                    if num < mid:
                        count += 1
                if count < mid:
                    # 比 4 小的个数，最多就只能是 3
                    # 所以重复的肯定不是 [1,2,3]，不能排除 4
                    # 因为左边不变，所以取中点的时候，就要偏右
                    left = mid
                else:
                    # 比 4 小的个数，达到 4 或者更多
                    # 重复的就落在 [1,2,3]
                    right = mid - 1
            # 跳出循环肯定是因为 start = end
            return left

参考资料：《剑指 Offer》（第 2 版）第 3 题：数组中重复的数字。