[LeetCode] Find Median from Data Stream

思路是使用一个minHeap和maxHeap。不知道有没有更好的方法。

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

class MedianFinder {       private PriorityQueue<Integer> minHeap;     private PriorityQueue<Integer> maxHeap;       public MedianFinder() {         minHeap = new PriorityQueue<Integer>();         maxHeap = new PriorityQueue<Integer>(500, Collections.reverseOrder());     }         // Adds a number into the data structure.     public void addNum(int num) {         if (maxHeap.size() == 0 || num <= maxHeap.peek()) {             maxHeap.add(num);         }         else {             minHeap.add(num);         }         if (maxHeap.size() - minHeap.size() >= 2) {             minHeap.add(maxHeap.poll());         }         else if (minHeap.size() > maxHeap.size()) {             maxHeap.add(minHeap.poll());         }     }         // Returns the median of current data stream     public double findMedian() {         double median = 0;         if (maxHeap.size() != 0) {             if ((maxHeap.size() + minHeap.size()) % 2 != 0) {                 median = (double) maxHeap.peek();             }             else {                 median = (double) (maxHeap.peek() + minHeap.peek()) / 2;             }         }         return median;     } };