關(guān)于我的 Leetcode 題目解答，代碼前往 Github：https://github.com/chenxiangcyr/leetcode-answers

如何理解中位數(shù) Median:

Dividing a set into two equal length subsets, that one subset is always greater than the other.
中位數(shù) Median 可以將一個(gè)集合分為長(zhǎng)度相等的兩個(gè)子集合，其中一個(gè)子集合的元素都大于另一個(gè)子集合。

LeetCode題目：4. Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
假設(shè)集合A的長(zhǎng)度為m，集合B的長(zhǎng)度為n。
將集合A從位置 i 處分開，得到左右兩個(gè)部分：

left_A = A[0]....A[i - 1] 長(zhǎng)度為 i
right_A = A[i]....A[m - 1] 長(zhǎng)度為 m - i

將集合B從位置 j 處分開，得到左右兩個(gè)部分：

left_B = B[0]....B[j - 1] 長(zhǎng)度為 j
right_B = B[j]....B[n - 1] 長(zhǎng)度為 n - j

令 left_part = left_A + left_B, right_part = right_A + right_B。
如果我們可以確保如下兩個(gè)條件成立：

• 條件1：len(left_part)=len(right_part)
• 條件2：max(left_part) ≤ min(right_part)

則可以得到中位數(shù)Median = (max(left_part) + min(right_part)) / 2

要確保如上兩個(gè)條件成立，則需要保證：

• 條件1：i + j == m + n - i - j
• 條件2：A[i - i] <= B[j] && B[j - 1] <= A[i]

具體代碼如下：

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        
        // 確保數(shù)組A長(zhǎng)度小于數(shù)組B長(zhǎng)度，因此確保 j 不會(huì)為負(fù)數(shù)
        if (m > n) {
            int[] temp = A;
            A = B;
            B = temp;
            
            int tmp = m;
            m = n;
            n = tmp;
        }
        
        int iMin = 0;
        int iMax = m;
        int halfLen = (m + n + 1) / 2;
        
        while (iMin <= iMax) {
            // 初始從數(shù)組A的中間分隔
            int i = (iMin + iMax) / 2;
            
            // 確保條件1：`i + j == m + n - i - j`
            int j = halfLen - i;
            
            // i is too small
            if (i < iMax && B[j-1] > A[i]){
                iMin = iMin + 1;
            }
            // i is too big
            else if (i > iMin && A[i-1] > B[j]) {
                iMax = iMax - 1;
            }
            // 確保條件2：`A[i - i] <= B[j] && B[j - 1] <= A[i]`
            else {
                int maxLeft = 0;
                if (i == 0) {
                    maxLeft = B[j-1];
                }
                else if (j == 0) {
                    maxLeft = A[i-1];
                }
                else {
                    maxLeft = Math.max(A[i-1], B[j-1]);
                }
                
                if ( (m + n) % 2 == 1 ) {
                    return maxLeft;
                }

                int minRight = 0;
                if (i == m) {
                    minRight = B[j];
                }
                else if (j == n) {
                    minRight = A[i];
                }
                else {
                    minRight = Math.min(B[j], A[i]);
                }

                return (maxLeft + minRight) / 2.0;
            }
        }
        
        return 0.0;
    }
}

LeetCode題目：295. Find Median from Data Stream
Design a data structure that supports the following two operations:
void addNum(int num) - Add a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.

基本思想：

• 使用一個(gè)最大堆 PriorityQueue 存儲(chǔ)左半部分
• 使用一個(gè)最小堆 PriorityQueue 存儲(chǔ)右半部分
• 保證 maxHeap.size() - minHeap.size() <= 1

具體代碼如下：

class MedianFinder {
    // store the smaller half of the input numbers
    private PriorityQueue<Integer> maxHeap;
    
    // store the larger half of the input numbers
    private PriorityQueue<Integer> minHeap;
    
    
    /** initialize your data structure here. */
    public MedianFinder() {
        // Should provide comparator to support max heap
        maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
        
        
        // by default, PriorityQueue is a min heap
        minHeap = new PriorityQueue<Integer>();
    }
    
    public void addNum(int num) {
        
        maxHeap.add(num);
        
        // balancing
        minHeap.add(maxHeap.peek());
        maxHeap.poll();
        
        // maintain size property
        if(maxHeap.size() < minHeap.size()) {
            maxHeap.add(minHeap.peek());
            minHeap.poll();
        }
    }
    
    public double findMedian() {
        if((maxHeap.size() + minHeap.size()) % 2 == 0) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
        else {
            return maxHeap.peek();
        }
    }
}