leetcode 697. 数组的度(python)

短命女 2022-05-14 16:52 173阅读 0赞

给定一个非空且只包含非负数的整数数组 `nums`, 数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是找到与 `nums` 拥有相同大小的度的最短连续子数组，返回其长度。

**示例 1:**

输入: [1, 2, 2, 3, 1]
    输出: 2
    解释: 
    输入数组的度是2，因为元素1和2的出现频数最大，均为2.
    连续子数组里面拥有相同度的有如下所示:
    [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
    最短连续子数组[2, 2]的长度为2，所以返回2.

**示例 2:**

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

**注意:**

*  `nums.length` 在1到50,000区间范围内。
 *  `nums[i]` 是一个在0到49,999范围内的整数。

class Solution(object):
        def findShortestSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            counts = collections.Counter(nums)
            left, right = {}, {}  #定义两个字典，存左右边界
            for i, num in enumerate(nums):
                #如果字典中包含有给定键，则返回该键对应的值，否则返回为该键设置的值。这样一来取得都是左边的
                left.setdefault(num, i) 
                #for 循环过程中，每一次都会更新值，最后一次执行时，right存下的都是最右边的边界
                right[num] = i
            degree = max(counts.values())
            res = min(right[num]-left[num]+1 for num in counts.keys() if counts[num] == degree)
            return res

知识点一：enumerate()

enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。Python 2.3. 以上版本可用，2.6 添加 start 参数。

>>>seq = ['one', 'two', 'three']
    >>> for i, element in enumerate(seq):
    ...     print i, element
    ... 
    0 one
    1 two
    2 three

知识点二：setdefault()

Python 字典 setdefault() 函数和[get() 方法][get_]类似, 如果键不存在于字典中，将会添加键并将值设为默认值。如果字典中包含有给定键，则返回该键对应的值，否则返回为该键设置的值。

dict.setdefault(key, default=None)

[get_]: http://www.runoob.com/python/att-dictionary-get.html