• Priority queue(优先队列的常见用法)和算法题(数据流中的中位数)


    一、Priority queue底层构建的结构是完全二叉树默认构建的是小顶堆

    二、Lambda表达式法书写比较器接口:

    小顶堆基本语法的默认表达形式:

    PriorityQueue<Integer> heap = new PriorityQueue<Integer>((u1,u2)->u1-u2);

     需要大顶堆时,做微调:将u1-u2换成u2-u1即可

    PriorityQueue<Integer> heap = new PriorityQueue<Integer>((u1,u2)->u2-u1);

    三、Lambda表达式的条件可根据实际情况调整

    算法案例题

    数据流中的中位数

    题目内容:如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值,如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

    例如,

    [2,3,4] 的中位数是 3

    [2,3] 的中位数是 (2 + 3) / 2 = 2.5

    设计一个支持以下两种操作的数据结构:

    void addNum(int num) - 从数据流中添加一个整数到数据结构中。
    double findMedian() - 返回目前所有元素的中位数。
    示例 1:

    输入:
    ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
    [[],[1],[2],[],[3],[]]
    输出:[null,null,null,1.50000,null,2.00000]

    来源:力扣(LeetCode)
    链接:https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    代码:

    1. PriorityQueue left;
    2. PriorityQueue right;
    3. /** initialize your data structure here. */
    4. public MedianFinder() {
    5. left = new PriorityQueue<>((n1,n2)->n2-n1);/*大顶堆*/
    6. right = new PriorityQueue<>(); /*小顶堆*/
    7. }/*大顶堆的开口接着小顶堆的开口,数据在两个堆里排列,相当于从小到大顺序排*/
    8. public void addNum(int num) {
    9. left.add(num);
    10. right.add(left.poll());
    11. if(left.size()+1/*如果右边太多了,就拉到左边*/
    12. left.add(right.poll());/*右边数目要不等于左边,要不比左边多一个*/
    13. }
    14. }
    15. public double findMedian() {
    16. if(right.size()>left.size()){
    17. return right.peek();
    18. }
    19. return (double)(left.peek()+right.peek())/2;
    20. }

  • 相关阅读:
    cpp qt 一个奇怪的bug
    TortoiseSVN小乌龟的使用
    Pytorch训练神经网络完整步骤:搭建一个完整的神经网络(以用于Mnist手写数字识别的卷积神经网络为例)
    【测开求职】2023秋招百度三面面经
    链接文件学习(七):英飞凌MCU Tasking编译器LSL链接文件解析 及代码变量定位方法
    远程debug调试
    SpringCloud:使用Nacos作为配置中心
    Java安全之Tomcat6 Filter内存马
    机器学习模型1——线性回归和逻辑回归
    人工智能与机器学习
  • 原文地址:https://blog.csdn.net/zhan_qian/article/details/126107104