LeetCode 面试题 17.20. 连续中值(大顶堆+小顶堆）

class MedianFinder {
    

    /** initialize your data structure here. */
    private PriorityQueue<Integer> minHeap;//小顶堆
    private PriorityQueue<Integer> maxHeap;//大顶堆
    public MedianFinder() {
    
        minHeap = new PriorityQueue<Integer>(new Comparator<Integer>(){
    
            public int compare(Integer i1,Integer i2){
    
                return i1.compareTo(i2);
            }
        });
        maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>(){
    
            public int compare(Integer i1,Integer i2){
    
                return i2.compareTo(i1);
            }
        });
    }
    public void makeBalance(){
    
        if(minHeap.size() > maxHeap.size()){
    
            maxHeap.offer(minHeap.poll());
        }
        else if(maxHeap.size() > minHeap.size() + 1){
    
            minHeap.offer(maxHeap.poll());
        }
    }
    public void addNum(int num) {
    
         if(maxHeap.size() == 0 || num <= maxHeap.peek())
            maxHeap.offer(num);
          else
            minHeap.offer(num);
        makeBalance();
    }
    
    public double findMedian() {
    
         int k = minHeap.size() + maxHeap.size();
         return k % 2 == 0 ? ((double) minHeap.peek() + maxHeap.peek()) / 2 : maxHeap.peek();

    }
}

/** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj = new MedianFinder(); * obj.addNum(num); * double param_2 = obj.findMedian(); */