1+ package hard ;
2+
3+ import java .util .*;
4+
5+ /**
6+ * Created by fishercoder1534 on 10/3/16.
7+ */
8+ public class FindMedianFromDataStream {
9+ }
10+
11+ class MedianFinder {
12+ //Thanks to Stefan's post: https://discuss.leetcode.com/topic/27521/short-simple-java-c-python-o-log-n-o-1
13+ /**
14+ * The idea is for sure to use two heaps, one is max heap, one is min heap, we always let the max heap be one element
15+ * bigger than min heap if the total number of elements is not even.
16+ * we could always get the median in O(1) time.
17+ * 1. use Long type to avoid overflow
18+ * 2. negate the numbers for small heap to save the effort for writing a reverse comparator, brilliant!*/
19+ private Queue <Long >large =new PriorityQueue <Long >();
20+ private Queue <Long >small =new PriorityQueue <Long >();
21+
22+ // Adds a number into the data structure.
23+ public void addNum (int num ) {
24+ large .offer ((long )num );
25+ small .offer (-large .poll ());
26+ if (large .size () <small .size ())large .offer (-small .poll ());
27+ }
28+
29+ // Returns the median of current data stream
30+ public double findMedian () {
31+ if (large .size () >small .size ())return large .peek ();
32+ return (large .peek ()-small .peek ())/2.0 ;
33+ }
34+
35+ };
36+
37+ // Your MedianFinder object will be instantiated and called as such:
38+ // MedianFinder mf = new MedianFinder();
39+ // mf.addNum(1);
40+ // mf.findMedian();