LeetCode 697. 数组的度
原题链接
简单
作者:
三年后必进FLAG
,
2021-02-20 10:38:40
,
所有人可见
,
阅读 241
思路
- 关键性质:最短子数组的首尾一定是构成该子数组的度的数
- 用一个哈希表
unordered_map<int, vector<int>> hash
记录每个数出现的频次、首尾位置
- 然后选出出现次数最多且首尾位置最近(长度最短)的数
代码
class Solution {
public:
int findShortestSubArray(vector<int>& nums) {
// 关键性质:最短子数组的首尾一定是构成度的数
unordered_map<int, vector<int>> hash;
int n = nums.size();
for(int i = 0; i < n; i ++){
if(hash.count(nums[i])){
hash[nums[i]][0] ++;
hash[nums[i]][2] = i;
}
else{
hash[nums[i]] = {1, i, i};
}
}
int maxDeg = 0, minLen = INT_MIN;
for(auto& [_, vec] : hash){
int len = vec[2]-vec[1]+1;
if(maxDeg < vec[0]){
maxDeg = vec[0];
minLen = len;
}
else if(maxDeg == vec[0]){
if(minLen > len){
minLen = len;
}
}
}
return minLen;
}
};