找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0 ～ n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
2 <= n <= 100000
一解
利用临时变量tmp存储已遍历的数：
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
tmp = []
for num in nums:
if num not in tmp:
tmp.append(num)
# 如果该数在 tmp 中，就确认有重复
else:
return num
-
执行用时：5692ms，在所有 Python3 提交中击败了 7.74%的用户
-
内存消耗：23.5MB，在所有 Python3 提交中击败了 27.25%的用户
一解的问题在于：
-
使用临时数组消耗大量内存
-
if num not in tmp的 in 操作是 O(n) ，浪费时间
二解
使用原地 hash 思想，在位置 0 遇到元素 6 ，判断其值和位置 6 的值 10 是否相同。
不相同：将两者互换
相同：找到重复值，返回结果
一直重复此过程：
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
# 只有 i != nums[i] 时，才说明要判断的两个元素在两个位置，即 nums[i] 和 nums[nums[i]] 不是同一个元素
if i != nums[i]:
if nums[i] == nums[nums[i]]:
return nums[i]
tmp = nums[i]
nums[i], nums[tmp] = nums[tmp], nums[i]
-
执行用时：32ms，在所有 Python3提交中击败了99.79%的用户
-
内存消耗：23.4MB，在所有 Python3提交中击败了52.83%的用户