Degree of an Array

题目

Given a non-empty array of non-negative integersnums, 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 ofnums, that has the same degree asnums.

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: nums.lengthwill be between 1 and 50,000.nums[i]will be an integer between 0 and 49,999.

思路分析

这道题应该是首先通过hashtable来得到每一个integer在array中出现的次数，注意可能有多个integer出现的次数一样。把出现次数最多的integer放在一个list中，然后分别得到每一个数的第一个index和最后一个index，然后就可以得到每一个数的min length，最后求这些min length中最小的。

• [ ] 首先，通过hashtable得到每一个integer在array中出现的次数，基本的实现方式就是创建一个dictionary，然后遍历array：

hmap = {}
for num in nums:
    hmap[num] = hmap.setdefault(num, 0) + 1

另外一个简单的实现方法就是调用Python的collections类中的Counter方法，可以实现同样的结果

hmap = collections.Counter(nums)

• [ ] 在得到array中每一个数字出现的次数之后，就要找到出现次数最多的那些elements：

degreeNums = []
degree = max(hmap.values())
for key in hmap.keys():
    if hmap[key] == degree: degreeNums.append(key)

• [ ] 然后是计算每一个出现次数最多的element的min length，那就是要得到这个element的第一个index和最后一个index。

如何得到第一个index很简单，就是nums.index(num)来得到。那么如何得到最后一个index呢？Python中的list没有得到最后一个index的方法，我的思路是将这个array反转成revNums，通过得到反转后第一个index来得到原数组中的最后一个index。这个方法可以实现，但是时间复杂度会增加很多，因为每一个元素都要用O(n)的时间复杂度来得到其min length：

revNums = list(reversed(nums))
length = len(nums) - revNums.index(num) - nums.index(num)

能不能有更快的方法来得到元素的第一个index和最后一个index呢？我们可以通过enumerate array的时候用dictionary来记录每一个元素的第一个index和最后一个index

firstIndex, lastIndex = {}, {}
for index, value in enumerate(nums):
    firstIndex.setdefault(value, index)
    lastIndex[value] = index

• [ ] 最后是要得到每一个出现次数最多的element的min length中最小的那个并返回，基本实现为

result = len(nums)
for num in degreeNums:
    if lastIndex[num] - firstIndex[num] + 1 < result: result = lastIndex[num] - firstIndex[num] + 1
return result

这个在Python中也可以优化为：

return min(lastIndex[num] - firstIndex[num] + 1 for num in degreeNums)

最终优化后的Python代码实现：

class Solution(object):
    def findShortestSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        firstIndex, lastIndex = {}, {}
        hmap = collections.Counter(nums)
        degree = max(hmap.values())
        degreeNums = [key for key in hmap.keys() if hmap[key] == degree]
        for index, value in enumerate(nums):
            firstIndex.setdefault(value, index)
            lastIndex[value] = index
        return min(lastIndex[num] - firstIndex[num] + 1 for num in degreeNums)