=============================
面试题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

---------------------------------------

**方法一：** 哈希表

.. tip::

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

    ``此法需要额外的空间开销``

.. note::

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

.. code:: python

    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

---------------------------------------

**方法二：** 下标定位法

.. tip::

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

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

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

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

    ``此法改变了原数组``

.. note::

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

.. code:: python

    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]

---------------------------------------

.. todo:: 不改变原数组解法