Simple Java using 2 heaps, beats 82% runtime:)


  • 0
    S
    public class MedianFinder {
    
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(10);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(10, new Comparator<Integer>(){
            public int compare(Integer a, Integer b) {
                return b.compareTo(a);
            }
        });
    
        // Adds a number into the data structure.
        public void addNum(int num) {
            if(minHeap.size() == 0 && maxHeap.size() == 0) {
                maxHeap.add(num);
                return;
            }
            if(minHeap.size() < maxHeap.size()) {
                if(maxHeap.peek() > num) {
                    minHeap.add(maxHeap.poll());
                    maxHeap.add(num);
                }
                else {
                    minHeap.add(num);
                }
            } else if(minHeap.size() > maxHeap.size()){
                if(minHeap.peek() > num) {
                    maxHeap.add(num);
                }
                else {
                    maxHeap.add(minHeap.poll());
                    minHeap.add(num);
                }
            } else {
                if(minHeap.peek() > num) {
                    maxHeap.add(num);
                } else {
                    maxHeap.add(minHeap.poll());
                    minHeap.add(num);
                }
            }
        }
    
        // Returns the median of current data stream
        public double findMedian() {
            double med = 0;
            if((minHeap.size()+maxHeap.size()) % 2 ==1) {
                return (double) maxHeap.peek();
            }
            return (double)(maxHeap.peek()+minHeap.peek())/2;
        }
    };
    
    // Your MedianFinder object will be instantiated and called as such:
    // MedianFinder mf = new MedianFinder();
    // mf.addNum(1);
    // mf.findMedian();

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.