数据结构与算法——Java实现 37.求数据流中位数——优先级队列实现

这辈子最蠢的想法就是快点长大

                                        —— 24.10.15

295. 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3 。
• 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。

• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

• double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

自定义分堆算法见文章：

写文章-CSDN创作中心

比较器

import java.util.Comparator;
import java.util.PriorityQueue;

public class LeetCode295_2MiddleInDataStream {
    // 添加元素
    public void addNum(int num) {
        if (leftMinHeap.size() == rightMaxHeap.size()){
            rightMaxHeap.offer(num);
            leftMinHeap.offer(rightMaxHeap.poll());
        }else {
            leftMinHeap.offer(num);
            rightMaxHeap.offer(leftMinHeap.poll());
        }
    }

    // 寻找中位数
    public double findMedian() {
        if (leftMinHeap.size() == rightMaxHeap.size()){
            return (leftMinHeap.peek() + rightMaxHeap.peek()) / 2.0;
        }else {
            return leftMinHeap.peek();
        }
    }

    // 大顶堆
    private PriorityQueue<Integer> leftMinHeap = new PriorityQueue<>(
            (a,b) -> Integer.compare(b,a) // 比较器对象Integer的compare方法比较
    );

    // 小顶堆
    private PriorityQueue<Integer> rightMaxHeap = new PriorityQueue<>(
            (a,b) -> Integer.compare(a,b) // 比较器对象Integer的compare方法比较
    );

    public static void main(String[] args) {
        // 小顶堆比较器
        //Comparator<Integer> cmp = (a, b) -> Integer.compare(a,b);
        // 大顶堆比较器
        Comparator<Integer> cmp = (a,b) -> Integer.compare(b,a);
        int a = 10;
        int b = 20;
        if(cmp.compare(a, b) > 0){
            System.out.println("上浮");
        }else {
            System.out.println("停止上浮");
        }
    }
}

通过调用不同对象切换不同的比较器，就可以切换大顶堆和小顶堆的实现

原文地址：https://blog.csdn.net/m0_73983707/article/details/142930476

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！