数据流中的中位数

最新推荐文章于 2025-02-10 18:36:35 发布

__William__

最新推荐文章于 2025-02-10 18:36:35 发布

阅读量5.7k

点赞数

分类专栏： leetcode 文章标签： leetcode

本文链接：https://blog.csdn.net/willduan1/article/details/53392940

版权

leetcode 专栏收录该内容

35 篇文章

订阅专栏

该博客探讨了如何在数据流中实时计算中位数，提出了几种解题思路，包括数组排序、排序链表、二叉搜索树、AVL树以及大顶堆和小顶堆的方法。对比了它们在插入和查找中位数时的时间复杂度，强调了在效率和退化情况下的优劣。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目：

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

解题思路：

有以下几种解题思路：

数组插入进去然后再排序，这种情况插入时间效率是O(n)，找中位数时间效率是O(1)。
排序的链表，两种时间复杂度和上面是一样的。
二叉搜索树，首先说一下平均的时间效率，插入的时间效率是O(logn)，找中位数的时间效率是O(logn)。然而当插入的时间顺序是排好序的数组的时候，二叉树就退化成了一个数组，插入时间效率是O(n)，找中位数的时间效率是O(n)。
AVL树，插入的时间效率是O(logn)，找中位数的时间效率是O(1)。
大顶堆和小顶堆。插入的时间效率是O(logn)，找中位数的时间效率是O(1)。

下面的代码使用一个大顶堆和小顶堆来完成：

PriorityQueue<Integer> min = new PriorityQueue();
PriorityQueue<Integer> max = new PriorityQueue(1000, Collections.reverseOrder());
//当JDK8的时候，可以直接写成，不再需要初始化容量
//PriorityQueue<Integer> max = new PriorityQueue(Collections.reverseOrder());

public void Insert(Integer num) {
    max.offer(num);
    min.offer(max.poll());
    if (max.size() < min.size()) {
        max.offer(min.poll());
    }
}

public Double GetMedian() {
    if (max.size() == min.size()) {
        return (max.peek() + min.peek())/2.0;
    }
    return (double)max.peek();
}

-----------EOF------------