算出degree相同的最小子列表.
degree是一个列表中出现相同元素的最大次数
Example 1:
Input: [1, 2, 2, 3, 1]
Output: 2
Explanation:
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.
Example 2:
Input: [1,2,2,3,1,4,2]
Output: 6
从原列表的degree开始, 求出每一个子列表, 计算列表的degree, 如果两个degree相同, 就是所求的结果
class Solution(object):
# 求出列表的degree
def findDegree(self, nums):
return max([nums.count(i) for i in set(nums)])
def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
rsts = []
degree = self.findDegree(nums)
for n in range(degree, len(nums)+1):
for k in range(n,len(nums)+1):
sub_degress = self.findDegree(nums[k-n:k])
#print(n, nums[k-n:k])
if sub_degress == degree:
return n
时间复杂度 O(n3),超时
# 计算最大degree的元素的最大距离
def findShortestSubArray(self, nums):
c = collections.Counter(nums)
first, last = {}, {}
for i, v in enumerate(nums):
first.setdefault(v, i)
last[v] = i
degree = max(c.values())
return min(last[v] - first[v] + 1 for v in c if c[v] == degree)
