Thinking process - Double Heap

Use a maxHeap to save smaller half of current input

Use a minHeap to save larger half of current input

Update two heap when a new integer added

Output

  • if even, then the median is (max in maxHeap + min in minHeap) / 2
  • if odd, then the min in minHeap

Time Complexity

O (logn) + O (1)

Mistakes

don't forget the cases that max in maxHeap might larger than min in minHeap

public class MedianFinder {
    PriorityQueue<Integer> minHeap;
    PriorityQueue<Integer> maxHeap;
    /** initialize your data structure here. */
    public MedianFinder() {
        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>(1, new Comparator<Integer>(){
            public int compare(Integer a, Integer b) {
                return (a - b) > 0 ? -1 : 1;
            }
        });
    }

    public void addNum(int num) {
        minHeap.add(num);
        if (minHeap.size() - 1 > maxHeap.size()) {
            maxHeap.add(minHeap.poll());
        } else {
            if (!maxHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
                minHeap.add(maxHeap.poll());
                maxHeap.add(minHeap.poll());
            }
        }


    }

    public double findMedian() {
        if (minHeap.size() != maxHeap.size()) {
            return (double)minHeap.peek();
        } else {
            double result = (minHeap.peek() + maxHeap.peek()) / 2.0;
            return result;
        }
    }
}

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

Thinking process - BST

https://discuss.leetcode.com/topic/53949/java-solution-using-bst-with-explanation-beats-99-at-time-of-posting

results matching ""

    No results matching ""