题目描述

题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

解题思路

遍历数组，然后记录每个数出现次数，不能直接在找到重复数就的返回重复数，必须要遍历完一次数组，确实没有出现不在 0~n-1的范围之间的数字，出现超范围数字可以直接返回-1。

时空分析

时间复杂度分析：由于是遍历数组，所以时间复杂度为 O(n)
空间复杂度分析：采用了字典，(HashMap 类型)，然后记录，故为 O(n)

Python 代码

from collections import defaultdict
class Solution(object):
    def duplicateInArray(self, nums):
        """
        :type nums: List[int]
        :rtype int
        """
        counters = defaultdict(lambda:0)
        range_right = len(nums)
        res = -1        # save duplicate num
        for num in nums:
            if num not in range(range_right):
                return -1   # none legal num in range 0 ~ n-1
            if counters[num] > 0:
                res = num
            else:
                counters[num] += 1
        return res