❓697. 数组的度
难度:简单
给定一个非空且只包含非负数的整数数组 nums
,数组的 度 的定义是指数组里任一元素出现频数的最大值。
你的任务是在 nums
中找到与 nums
拥有相同大小的度的最短连续子数组,返回其长度。
示例 1:
输入:nums = [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 。
示例 2:
输入:nums = [1,2,2,3,1,4,2]
输出:6
解释:
数组的度是 3 ,因为元素 2 重复出现 3 次。
所以 [2,2,3,1,4,2] 是最短子数组,因此返回 6 。
提示:
-
nums.length
在1
到50,000
范围内。 -
nums[i]
是一个在0
到49,999
范围内的整数。
💡思路:哈希表
使用哈希表,key
保存的是整数,value
保存一个数组,里面右三个数,分别为该整数出现的次数、第一次出现的位置,和最后一次出现的位置;
并设置变量max
和maxNum
,记录哪个整数出现的次数最大,及对应的value
置,在遍历数组的时候不断更新;
注意有可能数组中出现频率最大数的整数不止一个,这时我们要取较短的那个。
🍁代码:(Java、C++)
Java
class Solution {
public int findShortestSubArray(int[] nums) {
int max = 0;
int maxNum = 0;
HashMap<Integer, int[]> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
if(!map.containsKey(nums[i])){
int[] tem = {1, i, i};
map.put(nums[i], tem);
}else{
map.get(nums[i])[0]++;
map.get(nums[i])[2] = i;
}
if(map.get(nums[i])[0] > max){
max = map.get(nums[i])[0];
maxNum = nums[i];
}else if(map.get(nums[i])[0] == max && map.get(nums[i])[2] - map.get(nums[i])[1] < map.get(maxNum)[2] - map.get(maxNum)[1]){
maxNum = nums[i];
}
}
return map.get(maxNum)[2] - map.get(maxNum)[1] + 1;
}
}
C++
class Solution {
public:
int findShortestSubArray(vector<int>& nums) {
int max = 0;
int maxNum = 0;
unordered_map<int, vector<int>> map;
for(int i = 0; i < nums.size(); i++){
if(map.find(nums[i]) == map.end()){
map[nums[i]] = {1, i, i};
}else{
map[nums[i]][0]++;
map[nums[i]][2] = i;
}
if(map[nums[i]][0] > max){
max = map[nums[i]][0];
maxNum = nums[i];
}else if(map[nums[i]][0] == max && map[nums[i]][2] - map[nums[i]][1] < map[maxNum][2] - map[maxNum][1]){
maxNum = nums[i];
}
}
return map[maxNum][2] - map[maxNum][1] + 1;
}
};
🚀 运行结果:
🕔 复杂度分析:
-
时间复杂度:
O
(
n
)
O(n)
O(n),其中
n
为数组的长度。 - 空间复杂度: O ( n ) O(n) O(n),最坏情况下,哈希表和原数组等大。
题目来源:力扣。文章来源:https://www.toymoban.com/news/detail-433569.html
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-433569.html
注: 如有不足,欢迎指正!
到了这里,关于( 数组和矩阵) 697. 数组的度 ——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!