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 | class MedianFinder { public PriorityQueue < Integer > maxHeap; public PriorityQueue < Integer > minHeap; /** initialize your data structure here. */ public MedianFinder() { this.maxHeap = new PriorityQueue < > (Collections.reverseOrder()); this.minHeap = new PriorityQueue < > (); } public void addNum(int num) { this.maxHeap.add(num); this.minHeap.add(this.maxHeap.remove()); if (this.maxHeap.size() < this.minHeap.size()) { this.maxHeap.add(this.minHeap.remove()); } } public double findMedian() { return this.maxHeap.size() > this.minHeap.size() ? this.maxHeap.peek() * 1.0 : (this.maxHeap.peek() + this.minHeap.peek()) * 0.5; } } /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj = new MedianFinder(); * obj.addNum(num); * double param_2 = obj.findMedian(); */ |
Categories