题目地址：https://leetcode.com/problems/degree-of-an-array/description/open in new window
题目描述
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.
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
Note:
1、 nums.lengthwillbebetween1and50,000.；
2、 nums[i]willbeanintegerbetween0and49,999.；
题目大意
数组的度是出现次数最多的数字的出现次数。求一个最短子数组的长度，其度等于数组的度。
解题方法
求出最短相同子数组度的长度
题目大意：
给定非空非负整数数组，数组的度是指元素的最大出现次数。
寻找最大连续区间，使得区间的度与原数组的度相同。
想法很粗暴，直接求出整个数组的degree，然后找出所有的度等于该degree的数，找出最小度的数。
import collections
class Solution(object):
def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == len(set(nums)):
return 1
counter = collections.Counter(nums)
degree_num = counter.most_common(1)[0]
most_numbers = [num for num in counter if counter[num] == degree_num[1]]
scale = 100000000
for most_number in most_numbers:
appear = [i for i,num in enumerate(nums) if num == most_number]
appear_scale = max(appear) - min(appear) + 1
if appear_scale < scale:
scale = appear_scale
return scale
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
上面使用了Counter，下面的直接数，速度有一点提高。
import collections
class Solution(object):
def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums_set = set(nums)
if len(nums) == len(nums_set):
return 1
degree = max([nums.count(num) for num in nums_set])
most_numbers = [num for num in nums_set if nums.count(num) == degree]
scale = 100000000
for most_number in most_numbers:
appear = [i for i,num in enumerate(nums) if num == most_number]
appear_scale = max(appear) - min(appear) + 1
if appear_scale < scale:
scale = appear_scale
return scale
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
上面的不够快是因为重复计算了多次的nums.count(num)，避免重复计算可以使用字典进行保存。这个方法超出了96.7%的提交。
import collections
class Solution(object):
def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums_set = set(nums)
if len(nums) == len(nums_set):
return 1
num_dict = {num:nums.count(num) for num in nums_set}
degree = max(num_dict.values())
most_numbers = [num for num in nums_set if num_dict[num] == degree]
scale = 100000000
for most_number in most_numbers:
appear = [i for i,num in enumerate(nums) if num == most_number]
appear_scale = max(appear) - min(appear) + 1
if appear_scale < scale:
scale = appear_scale
return scale
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
还能更快吗？可以。把能压缩的列表表达式拆开，这样迭代一次就可以了。最后用了个提前终止，如果scale==degree说明这段子列表里没有其他元素了，一定是最短的。
这个方法超过了99.91%的提交。
import collections
class Solution(object):
def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums_set = set(nums)
if len(nums) == len(nums_set):
return 1
num_dict = {}
degree = -1
for num in nums_set:
_count = nums.count(num)
num_dict[num] = _count
if _count > degree:
degree = _count
most_numbers = [num for num in nums_set if num_dict[num] == degree]
scale = 100000000
for most_number in most_numbers:
_min = nums.index(most_number)
for i in xrange(len(nums)-1, -1, -1):
if nums[i] == most_number:
_max = i
break
appear_scale = _max - _min + 1
if appear_scale < scale:
scale = appear_scale
if scale == degree:
break
return scale
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
使用堆求最大次数和最小长度
二刷的时候，想到其实同时优化两个指标：最大次数和最小长度。所以，直接遍历所有的数字，同时统计它的次数，起始位置和结束位置，然后用一个堆，进行最大次数和最小长度的选择，对应的长度就是最小长度。
class Solution:
def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count = collections.defaultdict(tuple)
for i, num in enumerate(nums):
if num not in count:
count[num] = (1, i, i)
else:
count[num] = (count[num][0] + 1, count[num][1], i)
heap = [(-times, end - start + 1) for times, start, end in count.values()]
heapq.heapify(heap)
return heapq.heappop(heap)[1]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
保存最左边出现位置和最右边出现位置
使用两个字典，保存每个数字出现的最左边和最右边位置，这样的话，我们找到了出现次数等于数组的度的数字，然后看它的长度是不是最小的即可。
class Solution:
def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
left, right = dict(), dict()
count = collections.defaultdict(int)
for i, num in enumerate(nums):
if num not in left:
left[num] = i
right[num] = i
count[num] += 1
degree = max(count.values())
res = float("inf")
for num, c in count.items():
if c == degree:
res = min(res, right[num] - left[num] + 1)
return res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发