295.md

LeetCode 295 Find Median from Data Stream——hard

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

 
Follow up:
If all integer numbers from the stream are between 0 and 100, how would you optimize it?
If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

idea

思路：
1、直观想法的话，直接用列表，增加一个数就排序依次，这样addNum的复杂度是O（nlogn）、find是O（1）
2、优化：一般如果跟data stream数据流有关系，而且要排序的话，一定是用堆排序，也就是堆这个数据结构来处理
因为堆每次进行一次添加动作，复杂度只有logn，取得最大值或者最小值的复杂度为O（1）。
在这道题目里面，我们需要两个堆来完成
a、一个大顶堆small表示左半边的偏小的数、取堆顶可以取到最大值
一个小顶堆big表示右半边的偏大的数，取堆顶可以取到最小值
b、每次添加一个数要保证small、big两个堆的size之差<=1
&& big堆的最小值要比small堆的最大值大
c、这样子便可以取到中位数了，偶数的话，便是两个堆顶值之和除以2、奇数的话则是堆的size大的一方的堆顶值

optimize

With the help of java 8, you can simply write this (no initial capacity needed any more) :
PriorityQueue<Integer> max = new PriorityQueue(Collections.reverseOrder());

class MedianFinder {
   private Queue<Integer> small = new PriorityQueue(1, new Comparator<Integer>() {
		   public int compare(Integer o1, Integer o2) {
			   return o2 - o1; 
		   };
   });
	   
   private Queue<Integer> large = new PriorityQueue();
    // Adds a number into the data structure.
    public void addNum(int num) {
        large.add(num);
        small.add(large.poll());
        if (large.size() < small.size())
            large.add(small.poll());
    }

    // Returns the median of current data stream
    public double findMedian() {
        return large.size() > small.size()
               ? large.peek()
               : (large.peek() + small.peek()) / 2.0;
    }
}