# 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.

### 要完成的函数：

int findShortestSubArray(vector<int>& nums)

### 说明：

1、给定一个非空vector，里面含有非负数，vector的程度定义为“其众数出现的频率”，想找到一个尽可能短的连续子vector，使得该子vector的程度和vector的程度一样。

2、直接的想法，使用unordered_map遍历一遍vector，统计vector中元素出现的次数，然后再遍历一遍unordered_map找到出现最多次的元素（可能有多个），然后在vector中找到该元素的首次出现index和最后一次的index，得到长度。如果有多个元素，这里要求出最短的长度。

```    int findShortestSubArray(vector<int>& nums)
{
unordered_map<int,int>chuxian;
vector<int>elem;
int s1=nums.size();
int max1=0;
for(int i=0;i<s1;i++)//存储各个元素的出现次数
{
if(chuxian.count(nums[i]))
chuxian[nums[i]]++;
else
chuxian[nums[i]]=1;
}
for(unordered_map<int,int>::iterator iter=chuxian.begin();iter!=chuxian.end();iter++)
{//遍历map找到出现最多次的元素，插入到新定义的vector中
if(iter->second>max1)
{
elem.clear();
elem.push_back(iter->first);
max1=max(max1,iter->second);
}
else if(iter->second==max1)
elem.push_back(iter->first);
}
int i,j,t,min1=INT_MAX,s2=elem.size(),k=0;
while(k<s2)//每个元素都求出对应的长度，最后得到最短的长度
{
i=0;
j=s1-1;
t=elem[k];
k++;
while(i<s1)
{
if(nums[i]==t)
break;
i++;
}
while(j>=0)
{
if(nums[j]==t)
break;
j--;
}
min1=min(min1,j-i+1);
}
return min1;
}```

3、改进：

```    int findShortestSubArray(vector<int>& nums)
{
unordered_map<int,vector<int>> m1;//第二项是个vector
for(int i=0;i<nums.size();i++)
m1[nums[i]].push_back(i); //统计元素的出现位置
int max1=INT_MIN;
for(auto iter=m1.begin();iter!=m1.end();iter++) //遍历map找到出现的最多次数
max1=max(max1,int(iter->second.size()));//degree就是max1
int min1=INT_MAX;
for(auto iter=m1.begin();iter!=m1.end();iter++)//遍历map找到对应的元素，计算最短长度
{
if(iter->second.size()==max1)//
min1=min(min1,iter->second.back()-iter->second[0]+1);
}
return min1;
}```

205 篇文章43 人订阅

0 条评论

## 相关文章

3156

3126

### Java Collection、Map集合总结

依赖hashCode()和equals()两个方法进行保证元素唯一性，开发中使用开发工具自动生成就好。

822

3778

2496

### 面试必备：30 个 Java 集合面试问题及答案

Java集合框架为Java编程语言的基础，也是Java面试中很重要的一个知识点。这里，我列出了一些关于Java集合的重要问题和答案。

782

2093

1572

2871

922