每日三题-数组中的第K个最大元素、滑动窗口最大值、前K个高频元素

才疏学浅的木子

发布于 2022-11-20 08:47:20

77300

代码可运行

文章被收录于专栏：CSDN文章CSDN文章

运行总次数：0

代码可运行

👨‍💻个人主页： 才疏学浅的木子 🙇‍♂️ 本人也在学习阶段如若发现问题，请告知非常感谢 🙇‍♂️ 📒 本文来自专栏： 算法 🌈 算法类型：Hot100题 🌈

每日三题

数组中的第K个最大元素

解法一

暴力先排序再返回

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length-k];
    }
}

解法二

优先队列 维护一个长度为k的小根堆

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> p = new PriorityQueue<Integer>(k);
        for(int i = 0;i < nums.length;i++){
            if(p.size() == k){
                if(p.peek() < nums[i]){
                  p.poll();  
                  p.add(nums[i]);
                  
                }
                continue;      
            }else{
                p.add(nums[i]);
            }
            
        }
        return p.poll();
    }
}

滑动窗口最大值

解法一

滑动窗口 滑动窗口维护一个nums[i]值递减的序列

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if(k == 1 || len == 1 || len < k) return nums;
        LinkedList<Integer> list = new LinkedList<>();

        // 维护一个降序的双向队列 
        // 【1，3，-1】 = > [3,-1] =》[1,2]//下标
        for(int i = 0;i < k;i++){
            while(!list.isEmpty() && nums[i] > nums[list.peekLast()]){
                list.pollLast();
            }
            list.addLast(i);
        }
        int ans[] = new int[len-k+1];
        ans[0] = nums[list.peekFirst()];
        for(int i = k;i < len;i++){
            while(!list.isEmpty() && nums[i] > nums[list.peekLast()]){
                list.pollLast();
            }
            list.addLast(i);
            
            // 避免越界
            while(!list.isEmpty() && list.peekFirst() <= i-k){
                list.pollFirst();
            }
            ans[i-k+1] = nums[list.peekFirst()];
        }
        return ans;
    }
}

前K个高频元素

解法一

优先队列 先遍历获取频数数组再回去前k个

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < nums.length;i++){
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        PriorityQueue<Integer> p = new PriorityQueue<Integer>((num1,num2)->{
            return map.get(num1) - map.get(num2);
        });
        map.forEach((key,value)->{
            if(p.size() < k){
                p.add(key);
            }else{
                if(map.get(p.peek()) < map.get(key)){
                    p.poll();
                    p.add(key);
                }
            }
        });
        int ans [] = new int[k];
        int j = 0;
        while(!p.isEmpty()){
            ans[j++] = p.poll(); 
        }
        return ans;
    }
}