Leetcode#697. 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, 2 , 2, 3, 1 为[2,2],长度为2 再例如1,2,2,3,1,4,2 为2,2,3,1,4,2；长度为6

题解

思路： 首先需要找到出现次数最多的数，用map计数 单数出现次数最多的数可能是多个数，先存在temp数组中。 遍历数组比较最短长度。

C++代码

class Solution { public: int get_len(vector<int>nums, int index){//获取长度，查找第一次出现和最后一次出现位置 int s,e; for(int i=0; i<nums.size(); i++) { if(index == nums[i]){ s = i; break; } } for(int i=nums.size()-1; i>=0; i--) { if(index == nums[i]) { e = i; break; } } return e-s+1; } int findShortestSubArray(vector<int>& nums) { map<int,int>m; int mx=0, index, temp[nums.size()]; for(int i=0; i<nums.size(); i++) { m[nums[i]]++; if(mx < m[nums[i]])//找到出现次数最大值 { mx = m[nums[i]]; } } map<int,int>::iterator it; int k=0; for(it=m.begin(); it!=m.end(); it++) { if(it->second==mx){//将次数相同的数保存在temp数组中 temp[k++] = it->first; } } int mi=50005; for(int i=0; i<k; i++)//求数组的度 { mi = min(get_len(nums,temp[i]), mi); } return mi; } };

python代码

超时。。。

class Solution(object): def get_len(self, nums, index): e = 0 s = 0 for i in range(0, len(nums)): if index == nums[i]: s = i break for i in range(len(nums)-1, -1 ,-1): if index == nums[i]: e = i break return e-s+1 def findShortestSubArray(self, nums): """ :type nums: List[int] :rtype: int """ m = {} mx = 0 for i in range(0, len(nums)): m[nums[i]] = 0 for i in range(0, len(nums)): m[nums[i]] = m[nums[i]] + 1 if mx < m[nums[i]]: mx = m[nums[i]] temp = [] for key in m: if m[key] == mx: temp.append(key) mi = 50005 for i in range(0, len(temp)): mi = min(self.get_len(nums, temp[i]), mi) return mi