leetcode解題：(Hard) 295. Find Median from Data Stream

題目：https://leetcode.com/problems/find-median-from-data-stream/

描述：實作MedianFinder class，其中addNum()加入新元素，findMedian()找出目前輸入的元素中的中位數

class MedianFinder {

    public MedianFinder() {
        
    }
    
    public void addNum(int num) {
        
    }
    
    public double findMedian() {
        
    }
}

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

解題思路(1)：使用ArrayList儲存元素，輸入時使用二元搜尋(binary search)找出新元素排序好的位置，找尋中位數時因為輸入時已經排序好了，直接根據list長度為單或雙數回傳對應的中位數即可

程式碼：

class MedianFinder {
    List<Integer> nums;

    public MedianFinder() {
        nums = new ArrayList<Integer>();
    }
    
    public void addNum(int num) {
        int l = 0, r = nums.size()-1;
        while(l <= r) {
            if(num < nums.get((l+r)/2)) {
                r = (l+r)/2 - 1;
            }
            else l = (l+r)/2 + 1;
        }
        nums.add(l, num);
    }
    
    public double findMedian() {
        if(nums.size() % 2 == 0) {
            return (nums.get(nums.size() / 2) + nums.get(nums.size() / 2 - 1)) / 2.0;
        }
        else return nums.get(nums.size() / 2);
    }
}

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

時間複雜度：addNum()為O(logn (二元搜尋) + n (插入元素)) = O(n)，findMedian()為O(1)
空間複雜度：O(n)

---

解題思路(2)：因為中位數一定是數列的最中間1個元素或2個元素的平均值，我們可以把整個排序的數列拆成較小的那半部(small)與較大的那半部(large)，總元素數是單數時找small的最大值(單數時small會比large多一個元素)，雙數時取出small的最大值與large的最小值取平均值，要快速找最大值跟最小值就能使用資料結構的Max/Min heap。在Java中沒有單純的Heap，因此需要改用底層用Heap實作的Priority Queue。

程式碼：

class MedianFinder {
    //標準的PriorityQueue優先輸出最小的值
    //計算中位數時需要比較大的那半部輸出其中最小的值
    private PriorityQueue<Integer> large = new PriorityQueue<Integer>();
    //計算中位數時需要比較小的那半部輸出其中最大的值
    //因此建構時輸入Collections.reverseOrder()讓PriorityQueue改為優先輸出最大的值
    private PriorityQueue<Integer> small = new PriorityQueue<Integer>(Collections.reverseOrder());

    private boolean even = true;

    public MedianFinder() {
        
    }
    
    public void addNum(int num) {
        //已有的元素數為雙數，加上num變為單數
        if(even) {
            large.offer(num);               //先丟進large，再將large中最小的丟進small
            small.offer(large.poll());      //small比large多一個元素->中位數會是small裡的最大值
        }
        //已有的元素數為單數，加上num變為雙數
        else {
            small.offer(num);               //要讓small跟large數量平衡，先丟進samll中
            large.offer(small.poll());      //再把small中多出來的最大值丟進large->中位數會是small最大值與large最小值的平均
        }
        even = !even;
    }
    
    public double findMedian() {
        //元素數為雙數->中位數是small最大值與large最小值的平均
        if(even) {
            return (small.peek() + large.peek()) / 2.0;
        }
        //元素數為單數->中位數是small裡的最大值
        else {
            return small.peek();
        }
    }
}

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

時間複雜度：addNum()為O(logn)，findMedian()為O(1)
空間複雜度：O(n)

tags: leetcode hard binary search heap