4

Leetcode 295. Find Median from Data Stream

 3 years ago
source link: https://zxs.io/article/1328
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Leetcode 295. Find Median from Data Stream
当前位置：XINDOO > 算法 > 正文

题目链接295. Find Median from Data Stream

　　在一个有序数组中找中位数，但需要支持再数组中添加新的元素。本来是有序里的，可以很轻易就查到中位数，但如果添加新数字后，不一定有序。如果先对数组排序，那代价就比较大了，每次排序时间复杂度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;
    }
}
赏

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK