【LeetCode】697. Degree of an Array 解题报告

标签（空格分隔）： LeetCode

题目地址：https://leetcode.com/problems/degree-of-an-array/description/

题目描述：

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

Ways

方法一：

题目大意：
给定非空非负整数数组，数组的度是指元素的最大出现次数。

寻找最大连续区间，使得区间的度与原数组的度相同。

想法很粗暴，直接求出整个数组的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

上面使用了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

上面的不够快是因为重复计算了多次的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

还能更快吗？可以。把能压缩的列表表达式拆开，这样迭代一次就可以了。最后用了个提前终止，如果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

Date

2018 年 1 月 23 日