数组的度
给定一个非空且只包含非负数的整数数组 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 。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/degree-of-an-array
题解:
遍历数组,把元素值作为Key值存入HashMap集合,特殊的是要使用数组来存放Key值对应的Value值,数组的第一个位置存放元素出现的次数,第二个位置存放元素第一次出现时的下标,第三个位置存放元素最后一次出现时的下标,然后遍历HashMap集合,出现次数最多的元素的最后一次下标和第一次下标之差加一就是最短子数组的长度,若有多个元素出现次数相同,则取最短的子数组长度。代码如下:
class Solution {
public int findShortestSubArray(int[] nums) {
Map<Integer,int[]> map=new HashMap<Integer,int[]>();
//Value使用int数组,数组的第一个位置放对应Key出现的次数,第二个位置放第一次出现的位置,第三个位置放最后一次出现的位置
for(int i=0;i<nums.length;i++){
if(map.containsKey(nums[i])){
map.get(nums[i])[0]++;
map.get(nums[i])[2]=i;
}else{
map.put(nums[i],new int[]{1,i,i});
}
}
int du=0;
int val=nums.length;
Set<Map.Entry<Integer,int[]>> entry=map.entrySet();
for(Map.Entry<Integer,int[]> me:entry){
if(me.getValue()[0]>du){
du=me.getValue()[0];
val=me.getValue()[2]-me.getValue()[1]+1;
}else if(me.getValue()[0]==du){
val=Math.min(val,me.getValue()[2]-me.getValue()[1]+1);
}
}
return val;
}
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/153940.html