用两个堆最大堆和最小堆且保证两堆大小差最多为1且此时最大堆大小较大最小堆的值均大于最大堆class MedianFinder { PriorityQueueInteger p1; PriorityQueueInteger p2; public MedianFinder() { p1 new PriorityQueue((a,b) - b - a); p2 new PriorityQueue((a,b) - a - b); } public void addNum(int num) { if(p1.size() p2.size()){ p2.add(num); p1.add(p2.poll()); }else{ p1.add(num); p2.add(p1.poll()); } } public double findMedian() { if(p1.size() p2.size()){ return (p1.peek() p2.peek()) / 2.0; }else{ return p1.peek(); } } } /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj new MedianFinder(); * obj.addNum(num); * double param_2 obj.findMedian(); */