头像

ysmintor


访客:411

离线:2个月前



ysmintor
9个月前

题目描述

题目:在一个长度为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