求数据流中的中位数问题

博客 分享
0 140
张三
张三 2022-07-14 23:01:49
悬赏:0 积分 收藏

求数据流中的中位数问题

求数据流中的中位数问题

作者:Grey

原文地址: 求数据流中的中位数问题

题目链接

LeetCode 295. Find Median from Data Stream

主要思路

要得到数据流中的中位数,在偶数的情况下,要得到上下中位数求平均,在奇数的状态下,要得到中间位置的数,这里最关键的问题就是:如何快速找到中间位置(而且是动态的)。

我们可以准备两个堆,一个大根堆,一个小根堆,两个堆分别维持在一半左右的元素,且让这两个堆的堆顶始终保持中间位置的元素。这样就可以快速得到中位数需要的值了。具体操作如下:

第一个元素永远是先进大根堆。

接下来的元素,按如下规则进入:

如果接下来的元素比大根堆堆顶元素小,进大根堆,否则进入小根堆。

如果两个堆的大小差值已经达到2了,说明元素要向着一侧堆倾斜,这个时候,为了维持两个堆的平衡(即:始终可以拿到中位数需要的信息),从数量多的堆拿出一个放到数量少的堆,这样就让两个堆始终保持差值小于等于1。

此时,如果要得到中位数,通过如下规则就可以得到:

如果大根堆和小根堆数量一样,说明原始数据流是偶数个,那么直接拿出大根堆和小根堆的堆顶元素求和再除以2就是了。

如果大根堆和小根堆数量不一样(在这一步,只能是差1),那么就取多的那个堆的堆顶即为中位数。

完整代码如下

import java.util.Comparator;import java.util.PriorityQueue; class MedianFinder {        private final PriorityQueue<Integer> minHeap;        private final PriorityQueue<Integer> maxHeap;        public MedianFinder() {            minHeap = new PriorityQueue<>(Comparator.comparingInt((Integer o) -> o));            maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);        }        public void addNum(int num) {            if (maxHeap.isEmpty()) {                maxHeap.add(num);            } else {                if (maxHeap.peek() >= num) {                    maxHeap.add(num);                } else {                    minHeap.add(num);                }            }            int maxHeapSize = maxHeap.size();            int minHeapSize = minHeap.size();            if (maxHeapSize - minHeapSize == 2) {                minHeap.add(maxHeap.poll());            } else if (minHeapSize - maxHeapSize == 2) {                maxHeap.add(minHeap.poll());            }        }        public double findMedian() {            if (maxHeap.size() == minHeap.size()) {                return (maxHeap.peek() + minHeap.peek()) / 2d;            }            if (maxHeap.size() > minHeap.size()) {                return maxHeap.peek();            }            return minHeap.peek();        }}

更多

算法和数据结构笔记

posted @ 2022-07-14 22:03 Grey Zeng 阅读(8) 评论(0) 编辑 收藏 举报
回帖
    张三

    张三 (王者 段位)

    821 积分 (2)粉丝 (41)源码

     

    温馨提示

    亦奇源码

    最新会员