力扣刷题之优先队列

这篇具有很好参考价值的文章主要介绍了力扣刷题之优先队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言:优先队列底层是由大根堆或小根堆数据结构实现的。

前K个高频元素

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

题目解读:题目的要求是要我们找出在一个数组中找出k个出现频率最多的元素。

刚看到这个题目时候,直接冒出一个解决思路,就是利用桶排序的思想, 定义一个很大长度的数组,数组哪个位置有数,那就在哪个下标所在位置加一,然后排序,取出前k个最大值。


但是,如果利用这种思想来做题,直接大大浪费了很多的空间,还有一些没有必要的时间。

所有就引出了哈希表这个数据结构。我们可以把数组中出现的元素值作为哈希表的key值,然后出现的频率作为它的value,在遍历一遍数组之后,哈希表已经存储完毕了,再将哈希表进行排序,就可以得到前k个最大元素了。

public class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] ak = new int[k];
        int cnt = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }

        // 根据哈希表的Value值进行的排序
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort(Map.Entry.comparingByValue(Comparator.reverseOrder()));

        for (int i = 0; i < k; i++) {
            ak[cnt++] = list.get(i).getKey();
        }

        return ak;
    }
}

虽说这样就可以做完了,但是它的时间复杂度是O(n*k),我们并不满足如此,如果使用优先队列,我们就可以将时间复杂度减少到O(n*logk)。如果k越大,两者时间复杂度还会更大。

大根堆其实是一颗二叉树,是一颗二叉平衡树,它的根结点就是最大的数,左边结点会小于右边结点。

public class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] ak = new int[k];
        HashMap<Integer, Integer> map = new HashMap<>();
        //这里是大顶堆
        // PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2)->pair2[1]-pair1[1]);

        //小根堆
         PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2)->pair1[1]-pair2[1]);
        for(int num : nums){
            map.put(num, map.getOrDefault(num,0) +1);   //default
           
        }
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            // pq.add(new int[]{entry.getKey(),entry.getValue()});
              if(pq.size()<k){//小顶堆元素个数小于k个时直接加
                pq.add(new int[]{entry.getKey(),entry.getValue()});
            }else{
                if(entry.getValue()>pq.peek()[1]){
                    //当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
                    pq.poll();
                    //弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
                    pq.add(new int[]{entry.getKey(),entry.getValue()});
                }
            }
        }
        for(int i =k-1;i >=0 ;i--){
            ak[i] = pq.poll()[0];
        }

        return ak;
    }
}

滑动窗口最大值

239. 滑动窗口最大值

给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 

示例 1:

输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2:

输入:nums = [1], k = 1
输出:[1]

 如果做完第一题,直接来做第二题的,肯定第一秒想到的是直接使用循环+大根堆来实现,那真的能实现吗?we can try

 

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        
        int cnt = 0;
        int len = nums.length;
        int[] ans = new int[len - k +1 ];
        for(int i=0;i <= len-k;i++){
            PriorityQueue<Integer> pq = new PriorityQueue(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
            });;
            for(int j = i;j < i+k ; j++)
                pq.add(nums[j]);

            ans[cnt++] = pq.poll();
        }
        return ans;
    }
}

力扣刷题之优先队列,leetcode,算法,职场和发展

直接一整个时间超限了。

那这个题目要怎么来做呢?

class myQueue{
    Deque<Integer> deque = new LinkedList<>();
    void poll(int val){
        if(!deque.isEmpty() && deque.peek() == val)
            deque.poll();
    }

    void add(int val){
        while (!deque.isEmpty() && val > deque.getLast()) {
            deque.removeLast();
        }
        deque.add(val);
    }

    int peek(){
        return deque.peek();
    }

}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
          if (nums.length == 1) {
            return nums;
        }
        int len = nums.length - k + 1;
        //存放结果元素的数组
        int[] res = new int[len];
        int cnt = 0;

        myQueue myQueue = new myQueue();
        //先将前k的元素放入队列
        for (int i = 0; i < k; i++) {
            myQueue.add(nums[i]);
        }
        res[cnt++] = myQueue.peek();
        for (int i = k; i < nums.length; i++) {
            //滑动窗口移除最前面的元素,移除是判断该元素是否放入队列
            myQueue.poll(nums[i - k]);
            //滑动窗口加入最后面的元素
            myQueue.add(nums[i]);
            //记录对应的最大值
            res[cnt++] = myQueue.peek();
        }
        return res;
    }
}

 文章来源地址https://www.toymoban.com/news/detail-744803.html

到了这里,关于力扣刷题之优先队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【leetcode 力扣刷题】移除链表元素 多种解法

    题目链接:203.移除链表元素 题目内容: 理解题意:就是单纯的删除链表中所有值等于给定的val的节点。上一篇博客中介绍了链表的基础操作,在删除链表中节点时,需要注意的是头节点: 如果没有虚拟头节点,那么对头节点的删除需要做不同的处理,head = head-next; 如果有

    2024年02月12日
    浏览(48)
  • 【leetcode 力扣刷题】链表基础知识 基础操作

    在数据结构的学习过程中,我们知道线性表【一种数据组织、在内存中存储的形式】是线性结构的,其中线性表包括顺序表和链表。数组就是顺序表,其各个元素在内存中是连续存储的。 链表则是由 数据域 和 指针域 组成的 结构体 构成的,数据域是一个节点的数据,指针域

    2024年02月12日
    浏览(39)
  • 【leetcode 力扣刷题】回文串相关题目(KMP、动态规划)

    题目链接:5. 最长回文子串 题目内容: 题目就是要我们找s中的回文子串,还要是最长的。其实想想,暴力求解也行……就是遍历所有的子串,同时判断是不是回文串,是的话再和记录的最大长度maxlen比较,如果更长就更新。时间复杂度直接变成O(n^3)。 优化的点在于,假设子

    2024年02月09日
    浏览(48)
  • 【leetcode 力扣刷题】字符串翻转合集(全部反转///部分反转)

    题目链接:344. 反转字符串 题目内容: 题目中重点强调了必须 原地修改 输入数组,即不能新建一个数组来完成字符串的反转。我们注意到: 原来下标为0的,反转后是size - 1【原来下标是size - 1的,反转后是0】; 原来下标是1的,反转后是size - 2【原来下标是size -2的,反转后

    2024年02月11日
    浏览(46)
  • 【leetcode 力扣刷题】字符串匹配之经典的KMP!!!

    以下是能用KMP求解的算法题,KMP是用于字符串匹配的经典算法【至今没学懂………啊啊啊】 题目链接:28. 找出字符串中第一个匹配项的下标 题目内容: 题意还是很好理解的,要在字符串haystack中查找一个完整的needle,即字符串匹配。 暴力求解就是用 两层循环 :haystack从第

    2024年02月09日
    浏览(42)
  • 力扣刷题-动态规划算法3:完全背包问题

    问题描述: 1)有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。 2) 每件物品都有无限个(也就是可以放入背包多次) (比0-1背包多出的条件) 3) 求解将哪些物品装入背包里物品价值总和最大。 求解步骤: 1)首先遍历物品,然

    2023年04月13日
    浏览(58)
  • 【leetcode 力扣刷题】数学题之除法:哈希表解决商的循环节➕快速乘求解商

    题目链接:166. 分数到小数 题目内容: 题目是要我们把一个分数变成一个小数,并以字符串的形式返回。按道理,直接将分子numerator除以分母denominator就得到了小数,转换成string返回就好。题目要求里指出了特殊情况—— 小数部分如果有循环,就把循环节括在括号里 。 那么

    2024年02月10日
    浏览(40)
  • 力扣刷题之旅:高级篇(六)—— 网络流算法:Edmonds-Karp 算法与实际应用

               力扣(LeetCode) 是一个在线编程平台,主要用于帮助程序员提升算法和数据结构方面的能力。以下是一些力扣上的入门题目,以及它们的解题代码。              目录 引言  一、Edmonds-Karp 算法简介 二、算法实现 下面是使用 Python 实现的 Edmonds-Karp 算法:

    2024年02月22日
    浏览(41)
  • 【力扣刷题 | 第十七天】

    目录 前言: 55. 跳跃游戏 - 力扣(LeetCode) 45. 跳跃游戏 II - 力扣(LeetCode) 总结:         今天两道类型都是贪心算法,希望可以有所收获 给定一个非负整数数组  nums  ,你最初位于数组的  第一个下标  。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断

    2024年02月15日
    浏览(46)
  • 数据结构:力扣刷题

      给你一个  升序排列  的数组  nums  ,请你  原地  删除重复出现的元素,使每个元素  只出现一次  ,返回删除后数组的新长度。元素的  相对顺序  应该保持  一致  。然后返回  nums  中唯一元素的个数。 考虑  nums  的唯一元素的数量为  k  ,你需要做以下事情确

    2024年02月13日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包