295. Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:
[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) – Add a integer number from the data stream to the data structure.
double findMedian() – Return the median of all elements so far.
For example:

add(1)
add(2)
findMedian() -> 1.5
add(3)
findMedian() -> 2

思路: 寻找datastream或者array中的中位数, 可以用两个heap来实现,一个max heap,一个min heap。 每次加一个数先放到max heap,然后把max heap中poll一个数出来放到min heap。 同时要检查下max heap中的元素比min heap中要多;取中位数的时候,如果两个heap的size相同,则各poll一个元素出来算平均,否则max heap中poll出的就是median.
复杂度. addNum: O(logN), space: O(n), findMedian: O(1)

public class MedianFinder {
    PriorityQueue<Integer> higherPQ;
    PriorityQueue<Integer> lowerPQ;

    public MedianFinder() {
        higherPQ = new PriorityQueue<Integer>();
        lowerPQ = new PriorityQueue<Integer>(new Comparator<Integer>(){
            public int compare(Integer i1, Integer i2) {
                return i2 - i1;
            }
        });
    }

    // Adds a number into the data structure.
    public void addNum(int num) {
        higherPQ.add(num);
        lowerPQ.add(higherPQ.poll());

        if (higherPQ.size() < lowerPQ.size()) {
            higherPQ.add(lowerPQ.poll());
        }

    }

    // Returns the median of current data stream
    public double findMedian() {
        if (higherPQ.size() == lowerPQ.size()) {
            return ((double)higherPQ.peek() + lowerPQ.peek()) / 2.0;
        } else {
            return higherPQ.peek();
        }

    }
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();
// mf.addNum(1);
// mf.findMedian();
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s