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

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

找出数组中重复的数字。

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

示例 1：

输入：[2, 3, 1, 0, 2, 5, 3]

输出：2 或 3

限制：

2 <= n <= 100000

---

方法一： 哈希表

小技巧

遍历数组时判断是否在哈希表中存在，如果存在就找到了一个重复的数字。

此法需要额外的空间开销

备注

• 时间复杂度：O(n)

• 空间复杂度：O(n)

class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        a = {}
        for n in nums:
            if n in a:
                return n
            a[n] = n

---

方法二： 下标定位法

小技巧

如题描述，长度为 n 的数组，数字都在 0～n-1 的范围内，如果没有重复的数字， 则数字 i 应该出现在 nums[i] 位置，即 num[i] = i;

假设数组长度为 7，则数字范围是 [0, 6]。

我们有 7 个篮子，上面的编号为依次为 0 ~ 6，每个篮子里面有个球，球上面有编号，编号范围是 [0, 6]。

我们从第一个篮子开始检验，如果篮子里面球的编号和篮子编号一致，检验合格； 如果发现篮子里面球的编号和篮子编号不一致，我们怀疑 当前这个球 和 本该在这个篮子的球 偷偷换了位置，让当前这个球滚回与其编号一致的篮子，并把在它篮子里的球换回来； 如果换回来的球与篮子编号还不一致，同理，继续更换；如果在更换过程中，让当前球滚去其该再的位置时，发现已经有相同的球在那了，我们就找到了 重复的数字 。

此法改变了原数组

备注

• 时间复杂度：O(n)

• 空间复杂度：O(1)

class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for position, ball in enumerate(nums):
            # 篮子编号与球不一致，让球滚回其该再的位置
            while position != ball:
                #  滚回去发现，球的位置上已经有了一个自己，发现重复元素
                if nums[ball] == ball:
                    return ball
                nums[position], nums[ball] = nums[ball], nums[position]

---