【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: 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:

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 日

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

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

题目描述：

Ways

Date