python 寻找重复的数

综合编程 2018-05-27 阅读原文

给定一个包含 n
+ 1 个整数的数组 nums
,其数字都在 1 到 n
之间,包括 1 和 n
,可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。

示例 1:

输入: [1,3,4,2,2] 输出: 2

示例 2:

输入: [3,1,3,4,2]
输出: 3

说明:

  1. 不能
    更改原数组(假设数组是只读的)。
  2. 只能使用额外的 O(1) 的空间。
  3. 时间复杂度小于 O(n 2
    ) 。
  4. 数组中只有一个重复的数字,但它可能不止重复出现一次。
class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic = dict()
        for n in nums:
            dic[n] = dic.get(n, 0) + 1
            if dic[n] >= 2:
                return n
Waiting For You

责编内容by:Waiting For You阅读原文】。感谢您的支持!