Given a non-empty array of non-negative integers?nums, the?degree?of this array is defined as the maximum frequency of any one of its elements.
Your task is to find the smallest possible length of a (contiguous) subarray of?nums, that has the same degree as?nums.
class Solution(object):
? ? def findShortestSubArray(self, nums):
? ? ? ? """
? ? ? ? :type nums: List[int]
? ? ? ? :rtype: int
? ? ? ? """
? ? ? ? first, counter, res, degree = {}, {}, 0, 0
? ? ? ? for i, v in enumerate(nums):
? ? ? ? ? ? first.setdefault(v, i)
? ? ? ? ? ? counter[v] = counter.get(v, 0)+1
? ? ? ? ? ? if counter[v]>degree:
? ? ? ? ? ? ? ? degree = counter[v]
? ? ? ? ? ? ? ? res = i-first[v]+1
? ? ? ? ? ? elif counter[v]==degree:
? ? ? ? ? ? ? ? res = min(res, i-first[v]+1)
? ? ? ? return res
1 首先得到array的degree，調(diào)用collections.Counter().most_common(1)
2 怎么有效地去遍歷各個subarray
3 因為涉及到index和value，所以用enumerate
4 設(shè)置兩個dictionary，第一個first記錄v第一次出現(xiàn)的index，counter記錄出現(xiàn)的次數(shù)
5 依次遍歷array，得到每一個字符的first index和count，同時記錄返回長度
6 當(dāng)遍歷到后面，degree是一樣的時候，需要返回最小的長度
7?first.setdefault(v, i) 如果v在dict中，就直接返回初始index就行，如果不在dict中，把當(dāng)前的index寫進(jìn)去
8?counter[v] = counter.get(v, 0)+1, 這和first不同在于，counter是需要每次加1的，所以此處不用first.setdefault(v, i)，只是每次在get到的值的基礎(chǔ)上加1，初始化為0
