LeetCode刷题（57）～数组的度【巧妙！！！】

题目描述

给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

示例 1:

输入: [1, 2, 2, 3, 1]
输出: 2
解释: 
输入数组的度是2，因为元素1和2的出现频数最大，均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2，所以返回2.

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
 

示例 2:

输入: [1,2,2,3,1,4,2]
输出: 6

  

 

  
1
  
2
 

注意:

• nums.length 在1到50,000区间范围内。
• nums[i] 是一个在0到49,999范围内的整数。

解答 By 海轰

提交代码

int findShortestSubArray(vector<int>& nums) { int len=nums.size(); if(len==1) return 1; unordered_map<int,int> m; // 利用哈希 寻找度数 for(int i=0;i<len;++i) { ++m[nums[i]]; } int du=0; vector<int> a; for(unordered_map<int,int>::iterator it=m.begin();it!=m.end();++it) { du= du<it->second? it->second:du; } // 将最大度数对应的值加入 数组a for(unordered_map<int,int>::iterator it=m.begin();it!=m.end();++it) { if(it->second==du) a.push_back(it->first); } // 利用双指针 寻找最小长度 代码中变量命名有点问题【开始以为求最大值】 int maxlength=INT_MAX; for(int i=0;i<a.size();++i) { int b=a[i]; int left=0; int right=len-1; while(nums[left]!=b) ++left; while(nums[right]!=b) --right; maxlength= maxlength>(right-left+1)?(right-left+1):maxlength; } return maxlength; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
 

运行结果

提交代码（优化版）

int findShortestSubArray(vector<int>& nums) { if(nums.empty()) return 0; unordered_map<int,int> left;//记录数字第一次出现的位置 unordered_map<int,int> right;// 记录数字最后一次出现的位置 unordered_map<int,int> count;// 记录每个数字出现的次数 vector<int> maxNum;// 符合最大度的数字 可能不止一个哦 int maxCount = 0; for(int i = 0; i< nums.size(); i++){ if(!left.count(nums[i])) left[nums[i]] = i; right[nums[i]] = i; count[nums[i]]++; // 下面的代码非常巧妙 // 在上面求left right count的同时 // 下方依然求出了符合最大度数的数字 并保存在maxNum中 if(count[nums[i]] == maxCount) maxNum.push_back(nums[i]); else if(count[nums[i]] > maxCount){ maxNum.clear(); maxCount = count[nums[i]]; maxNum.push_back(nums[i]); } } // 寻找最小值 int ans = INT_MAX; for(int index : maxNum){ ans = min(ans,right[index] - left[index] + 1); } return ans; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
 

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/degree-of-an-array

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108038764