题目描述

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

示例

示例 1：

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

限制：
2 <= n <= 10000

解答方法

方法一：哈希表

思路

代码

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        nums_cnt = collections.Counter(nums)
        for i in nums_cnt:
            if nums_cnt[i] > 1:
                return i
###或者
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        dic = {}
        for num in nums:
            if num not in dic:
                dic[num] = 1
            else:
                return num

时间复杂度

O(n)

空间复杂度

O(1)

方法二：两两交换

思路

• 从头到尾扫描数组中的每个元素，比较数字m是否和小标i相等，
• 如果相等，扫描下一个
• 如果不相等，则将现有数字m和第m个数字作比较。
• 如果相等，则找到一个重复数字，
• 如果不想等，则交换。

代码

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return
        for i in range(len(nums)):
            while nums[i] != i:
                tmp = nums[i]
                if tmp == nums[tmp]:
                    return tmp
                else:
                    nums[i], nums[tmp] = nums[tmp] ,nums[i]

时间复杂度

O(n)

空间复杂度

O(1)