Leetcode 295. Find Median from Data Stream
Leetcode 295. Find Median from Data Stream
xindoo
发布于 2021-01-21 18:00:28
发布于 2021-01-21 18:00:28
在一个有序数组中找中位数，但需要支持再数组中添加新的元素。本来是有序里的，可以很轻易就查到中位数，但如果添加新数字后，不一定有序。如果先对数组排序，那代价就比较大了，每次排序时间复杂度O(n*log(n))，看discuss发现了一种很巧妙的解法，可以把添加数据的时间复杂度降低到O(log(n)) ，查询中位数O(1)。 这里我们需要用到优先队列，java里有现场的优先队列。准备两个优先队列，large里存比中位数大的数，small里存比中位数小的数。加入现在有n个数，large里存最大的n/2个数，很容易理解。但small里怎么存最小的n/2个数？ 这里有个很巧妙的地方，把数组里数取负存到small里，small优先队列里其实存的是数组中取负后最大的n/2个数，不就是原数组中最小的n/2个数吗？需要特别考虑到n位奇数时，large里存了n/2+1个数，small里存了n/2个数（其实多余的一个也存small里）。算中位数的时候，如果n为奇数，直接从large里去第一优先级的就好了，如果n是偶数，从large和small里各取一个求平均，注意small里取出的数要取负变换之后才能用。 代码如下，
import java.util.PriorityQueue;
import java.util.Queue;
class MedianFinder {
private Queue<Long> small = new PriorityQueue();
private Queue<Long> large = new PriorityQueue();
/** initialize your data structure here. */
public MedianFinder() {
}
public void addNum(int num) {
large.add((long) num);
small.add(-large.poll());
if (large.size() < small.size())
large.add(-small.poll());
}
public double findMedian() {
return large.size() > small.size() ? large.peek() : (large.peek() - small.peek()) / 2.0;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-02-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读