295. Find Median from Data Stream

四刷 06/2022

Version #1 Two Heaps

一开始写了一个bug就是无脑向maxHeap里面offer然后再balance

这样会造成很小的值被balance到larger half的minHeap里面

需要先和两个heap的peek value比较之后再往里面塞

Time - addNum O(logN), findMedian O(1)

Space - O(N)

Runtime: 183 ms, faster than 50.19% of Java online submissions for Find Median from Data Stream.

Memory Usage: 125.3 MB, less than 34.18% of Java online submissions for Find Median from Data Stream.

class MedianFinder {

    Queue<Integer> minHeap;

    Queue<Integer> maxHeap;

    public MedianFinder() {

        minHeap = new PriorityQueue<>();

        maxHeap = new PriorityQueue<>(Collections.reverseOrder());

    }

    

    public void addNum(int num) {

        // maxHeap contains smaller half of numbers

        // minHeap contains larger half of numbers

        // maxHeap.size() == minHeap.size()

        // or maxHeap.size() == minHeap.size() + 1;

        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {

            maxHeap.offer(num);

        } else {

            minHeap.offer(num);

        }

        if (maxHeap.size() < minHeap.size()) {

            maxHeap.offer(minHeap.poll());

        }

        if (maxHeap.size() > minHeap.size() + 1) {

            minHeap.offer(maxHeap.poll());

        }

    }

    

    public double findMedian() {

        if (maxHeap.size() == minHeap.size()) {

            return (maxHeap.peek() + minHeap.peek()) / 2.0;

        }

        return maxHeap.peek();

    }

}

/**

 * Your MedianFinder object will be instantiated and called as such:

 * MedianFinder obj = new MedianFinder();

 * obj.addNum(num);

 * double param_2 = obj.findMedian();

 */

三刷

Follow up


Version #1 Two Heaps

76.63 %
class MedianFinder {

    /** initialize your data structure here. */
    PriorityQueue<Integer> maxHeap, minHeap;
    public MedianFinder() {
        // 2 heap
        // maxHeap, minHeap -> to keep maxHeap size == minHeap size or minHeap size + 1
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }
   
    public void addNum(int num) {
        if (maxHeap.isEmpty()) {
            maxHeap.offer(num);
            return;
        }
        if (num < maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }
        adjust();
    }
   
    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
        return maxHeap.peek();
    }
   
    private void adjust() {
        while (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
        while (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        }
    }
}

二刷 LC

41.34 % 
class MedianFinder {

    // divide data into two parts ->   smaller half(size1) + larger half(size2)
    // always make sure that size1 == size2/ size2+1 -> if size1 == size2, median =  (maxOfSmallerHalf + minOfLargerHalf) / 2
    // else median = maxOfSmallerHalf
 
    /** initialize your data structure here. */
    PriorityQueue<Integer> smallerHalf;
    PriorityQueue<Integer> largerHalf;
    public MedianFinder() {
        smallerHalf = new PriorityQueue<>(10, Collections.reverseOrder());
        largerHalf = new PriorityQueue<>();
    }
 
    public void addNum(int num) {
        if (smallerHalf.isEmpty()) {
            smallerHalf.offer(num);
            return;
        }
     
        if (num <= smallerHalf.peek()) {
            smallerHalf.offer(num);
        } else {
            largerHalf.offer(num);
        }
         
        if (smallerHalf.size() < largerHalf.size()) {
            smallerHalf.offer(largerHalf.poll());
        } else if (smallerHalf.size() > largerHalf.size() + 1) {
            largerHalf.offer(smallerHalf.poll());
        }
    }
 
    public double findMedian() {
        if (smallerHalf.isEmpty()) {
            throw new RuntimeException("Empty number set");
        }
        if (smallerHalf.size() == largerHalf.size()) {
            return (smallerHalf.peek() + largerHalf.peek()) / 2.0;
        } else {
            return smallerHalf.peek();
        }
    }
}




一刷 LintCode
Using two heap
Time O(nlogn)
Space O(n)
public class Solution {
    /**
     * @param nums: A list of integers.
     * @return: the median of numbers
     */
    public int[] medianII(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) return nums;
        int[] med = new int[nums.length];
        //max heap
        PriorityQueue<Integer> heap1 = new PriorityQueue<>(1, new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                return b - a;
            }
        });
        //min heap
        PriorityQueue<Integer> heap2 = new PriorityQueue<>();
        int newNum;
        int currMed = nums[0];
        for (int i = 0; i < nums.length; i++) {
            newNum = nums[i];
            if (newNum <= currMed) heap1.offer(newNum);
            else heap2.offer(newNum);
            //heap2's size is at least 1 number
            if (heap1.size() < heap2.size()) {
                heap1.offer(heap2.poll());
            }
            if (heap1.size() > heap2.size() + 1) {
                heap2.offer(heap1.poll());
            }
            currMed = heap1.peek();
            med[i] = currMed;
        }
        return med;
    }
}