Leetcode295 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.

For example,

[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.

Example:

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

思路

两个priority queue，一个queue存较大部分一个queue寸较小部分

较小部分：small = new PriorityQueue((a,b) -> a - b);

较大部分：large = new PriorityQueue((a,b) -> b - a);

加入元素：如果large部分为空或者num数大于large的最小元素，则将num加入到large中，反之加入small中。加入后，比较large和small的大小，两个队列的size差不能超多1

计算中位数：如果small和large的大小相同，则取small的最大和large的最小值相加除以2.0；如果small的数量多，则取small数组的最大的那个。

代码

class MedianFinder {
    
    Queue<Integer> small;
    Queue<Integer> large;
    /** initialize your data structure here. */
    public MedianFinder() {
        small = new PriorityQueue<Integer>((a,b) -> b - a);
        large = new PriorityQueue<Integer>((a,b) -> a - b);
    }
    
    public void addNum(int num) {
        if(small.isEmpty()||num<=small.peek()){
            small.add(num);
        }else{
            large.add(num);
        }
        //balance left and right
        if(small.size()-large.size()>1){
            large.add(small.poll());
        }else if(small.size()<large.size()){
            small.add(large.poll());
        }
    }
    
    public double findMedian() {;
        double media =0;
        if(large.size()==small.size())
            media = (small.peek()+large.peek())/2.0;
        else
            media = small.peek();
        return media;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */