295.md

295. Find Median from Data Stream

题目链接

import java.util.ArrayList;
public class MedianFinder {
	ArrayList<Integer> al=new ArrayList<Integer>();
	public void addNum(int num) {
		al.add(num);
		//插入排序
		for (int i = 0; i < al.size(); i++) {
			if (num > al.get(i)) {
				for (int j = al.size()-1; j > i; j--) {
					al.set(j, al.get(j-1));
				}
				al.set(i, num);
				break;
			}
		}
	}
	public double findMedian() {
		int size = al.size();
		if(size % 2 == 1)
			return al.get(size/2);
		return (al.get(size/2-1)+al.get(size/2)) / 2.0;
	}
}

一个巧妙的做法

PriorityQueue<Integer> minHeap = new PriorityQueue<>();//heap is a minimal heap by default
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());//change to a maximum heap

// Adds a number into the data structure.
public void addNum(int num) {
    maxHeap.offer(num);
    minHeap.offer(maxHeap.poll());
    if (maxHeap.size() < minHeap.size())
        maxHeap.offer(minHeap.poll());
}

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

该算法的思路是设立两个堆，一个为大根堆，一个为小根堆。将排好序的序列前半部分放入大根堆中，将序列的后半部分放入小根堆中，要保证小根堆中的数目不多于大根堆中的数目。如果为奇数时，大根堆中的根元素就为中位数，如果为偶数，则需要将两个堆中的根元素相加求平均值。

同样的思路用c++实现：

class MedianFinder {
private:
    priority_queue<int> firstQ; // max_heap for the first half
    priority_queue<int, std::vector<int>, std::greater<int> > secQ; // min_heap for the second half
public:
    // Adds a number into the data structure.
    void addNum(int num) {
        if(firstQ.empty() || (firstQ.top()>num)) firstQ.push(num); // if it belongs to the smaller half
        else secQ.push(num); 

        // rebalance the two halfs to make sure the length difference is no larger than 1
        if(firstQ.size() > (secQ.size()+1))
        {
            secQ.push(firstQ.top());
            firstQ.pop();
        }
        else if(firstQ.size()+1<secQ.size())
        {
            firstQ.push(secQ.top());
            secQ.pop();
        }
    }

    // Returns the median of current data stream
    double findMedian() {
        if(firstQ.size() == secQ.size()) return firstQ.empty()?0:( (firstQ.top()+secQ.top())/2.0);
        else return (firstQ.size() > secQ.size())? firstQ.top():secQ.top(); 
    }
};