LeetCode Contest 54
这次比赛之后,下次再遇到O(n2)的题目,而且n < 1000的时候,一定要用C++!这是泪的教训啊😭
第一题Degree of an Array
在统计每个数字频率的同时,记录这个数字出现的最左和最右位置(l, r)。那么包含这个数字的最短数组的长度为r-l+1。
class Solution(object):
def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
cnt = {}
f = 0
for i, n in enumerate(nums):
if n not in cnt:
cnt[n] = [1, i, i]
else:
c, a, _ = cnt[n]
cnt[n] = [c+1, a, i]
f = max(f, cnt[n][0])
return min(v[2]-v[1]+1 for v in cnt.values() if v[0]==f)