E-697. Degree of an Array

Loading...LeetCode

# 这傻逼easy题写了老子半个小时
# 思路是, 用一个freq dict来记录频率, 用一个left字典记录数字最左的index, 一个right字典
# 记录数字最右的index.
# 1. 遍历整个nums, 在left字典里还没有num这个数字时, 往里面填一次index, 即最左index;
# 最右index看到相应的num就更新right[index]. 频率表看到num就+1
# 2. 通过max(dict.values())找到最大的频率(即degree)
# 3. 遍历freq dict, 如果找到拥有最大频率的num, 计算其right[num] - left[num] + 1, 并
# 更新当前最短的array长度. 最后输出结果
 
from collections import defaultdict
class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        left, right = {}, {}
        freq_map = defaultdict(int)
        for i, num in enumerate(nums):
            if not left[num]:
                left[num] = i
            right[num] = i
            freq_map[num] += 1
        
        res = len(nums)
        degree = max(freq_map.values())
        for num in freq_map:
            if freq_map[num] == degree:
                res = min(res, right[num] - left[num] + 1)
        
        return res