0697._Degree_of_an_Array.md

697. Degree of an Array

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/degree-of-an-array/

内容描述

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:

nums.length will be between 1 and 50,000.
nums[i] will be an integer between 0 and 49,999.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

拿个字典记一下ele和相应出现idx的lst就行了, beats 76.33%

class Solution(object):
    def findShortestSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        lookup = collections.defaultdict(list)
        for idx, num in enumerate(nums):
            lookup[num].append(idx)
        max_freq = max(len(lst) for lst in lookup.values())
        max_freq_eles = []
        for ele, lst in lookup.items():
            if len(lst) == max_freq:
                max_freq_eles.append(ele)
        if max_freq == 1:
            return 1
        else:
            return min(lookup[ele][-1] - lookup[ele][0] + 1 for ele in max_freq_eles)