# 【LeetCode】697. Degree of an Array 解题报告（Python）

xiaoxiao2021-02-28  11

## 题目描述

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.

## 解题方法

### 求出最短相同子数组度的长度

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

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

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

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

### 使用堆求最大次数和最小长度

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]

### 保存最左边出现位置和最右边出现位置

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

## 日期

2018 年 1 月 23 日 2018 年 11 月 16 日 —— 又到周五了！