文章
问答
冒泡
LeetCode 每日一题

image.png

思路

刚开始看到题目的时候有点懵🤣
示例1解释如下:
[1,2,2,3,1] 度为2,1出现的频率为2,2出现的频率也是为2,但是1的最左和最右之间的长度为5,而2的区间长度为2,所以输出为2
示例2解释如下:
[1,2,2,3,1,4,2] 由于2出现的频率为3,那么2的最左与最右之间的区间为[2,2,3,1,4,2],长度为6,所以最终输出为6
由于需要对数组元素中各个元素进行出现次数的计数,那么可以通过哈希map来存储对应元素出现的次数,此处借助 map.meger api map.merge接口再计数的时候能够进行获取当前元素出现频率的最大值。
在知道了值的情况下,需要再次遍历进行处理,此处借助滑动窗口的技巧。

代码

public class LC697 {
    public int findShortestSubArray(int[] nums){
        int len = nums.length, degree= 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i:nums){
            degree = Math.max(degree,map.merge(i,1,Integer::sum));
        }
        map.clear();
        int left = 0, right = 0, curDegree = 0, res = len;
        while(right<len){
            curDegree = Math.max(curDegree,map.merge(nums[right++], 1, Integer::sum));
            if(curDegree == degree){
                while(map.merge(nums[left], -1, Integer::sum) != degree -1){
                    left++;
                }
                curDegree = degree-1;
                res = Math.min(res, right-left);
            }
        }
        return res;
    }
数据结构与算法

关于作者

Kirago
个人站点 https://kiragoo.github.io/
获得点赞
文章被阅读