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

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

数组中的第K个最大元素


31bbc71b3e254e8d826ca266cbfcc216.png

解法一

暴力

先排序再返回

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();
    }
}


滑动窗口最大值


0891857aa1824732b77e29378cca1434.png

解法一

滑动窗口

滑动窗口维护一个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个高频元素


99f7719c468d422ea64f21e7ed054cae.png

解法一

优先队列

先遍历获取频数数组再回去前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;
    }
}


相关文章
|
API
代码随想录 Day10 栈与队列 LeetCode T239 滑动窗口的最大值 T347 前K个高频元素
代码随想录 Day10 栈与队列 LeetCode T239 滑动窗口的最大值 T347 前K个高频元素
48 0
|
3月前
|
算法 测试技术
【算法】二分算法——寻找旋转排序数组中的最小值
【算法】二分算法——寻找旋转排序数组中的最小值
|
6月前
|
机器学习/深度学习 算法 测试技术
【单调栈】3113. 边界元素是最大值的子数组数目
【单调栈】3113. 边界元素是最大值的子数组数目
|
6月前
|
算法
DAY-7 | 牛客-BM21 寻找旋转数组的最小元素:二分法分治思想真的很可靠
这是一个关于编程题目的摘要:题目是牛客网上的&quot;BM21 旋转数组的最小数字&quot;,要求找到旋转数组中的最小数字。题解介绍了使用二分查找算法来解决此问题,因为其时间复杂度优于暴力搜索的线性时间复杂度。二分查找的核心是通过比较中间元素与右端元素的大小,不断缩小搜索范围,最终找到最小值。代码示例展示了如何实现这个算法。总结中强调了二分查找适用于部分有序数组,并指出了解决这类问题的关键在于理解数组的二段单调性。
43 1
|
5月前
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
|
6月前
|
算法 测试技术 C#
【动态规划】【数论】【区间合并】3041. 修改数组后最大化数组中的连续元素数目
【动态规划】【数论】【区间合并】3041. 修改数组后最大化数组中的连续元素数目
|
6月前
|
算法 测试技术 C#
【单调栈】LeetCode2334:元素值大于变化阈值的子数组
【单调栈】LeetCode2334:元素值大于变化阈值的子数组
【单调栈】LeetCode2334:元素值大于变化阈值的子数组
|
6月前
每日一题——寻找旋转排序数组中的最小值(I)
每日一题——寻找旋转排序数组中的最小值(I)
|
6月前
|
算法 测试技术 C#
【滑动窗口】【差分数组】C++算法:K 连续位的最小翻转次数
【滑动窗口】【差分数组】C++算法:K 连续位的最小翻转次数
|
6月前
|
算法 程序员 测试技术
【算法训练-二分查找 二】【旋转二分】旋转排序数组的最小数字、旋转排序数组的指定数字
【算法训练-二分查找 二】【旋转二分】旋转排序数组的最小数字、旋转排序数组的指定数字
45 0
【算法训练-二分查找 二】【旋转二分】旋转排序数组的最小数字、旋转排序数组的指定数字