面試題解| Median of two Sorted Arrays

解題思路分析

這道題的直觀解法：就是掃一遍兩個數組，找到中間位置的那一個/兩個數，然後得到中位數。時間複雜度是 O(m+n)，其中 m 和 n 分別是數組 A 和數組 B 的長度。

深入分析

但是！面試官會這麼輕易就放過你嗎？顯然是不可能滴~~小編偷看了一下題目描述下的「challenge」標籤，原來這道題的最優解是 O(log(m + n)) 的複雜度。

(m + n) 是倆數組合併後的總長度  L，看到 O(log L) 這樣的複雜度，而且還是有序數組，能想到哪個算法嗎？沒錯，就是二分查找！那讓我們來試試——

1.如果我取出 A[i] ，用二分查找在數組 B 中找到 A[i] 可以插入的位置，假設 A[i] 在 B 中的插入位置是 j，那麼 A[i] 在整個合併數組中的位置就是 (i + j) ，因為要求的中位數的位置是 (m + n) / 2，通過比較 (i + j) 和 (m + n) / 2 的大小可以每次捨棄 A 的一部分，從而收斂數組 A。用同樣的方法可以收斂數組 B。但是這樣的複雜度是 O(log m * log n)，複雜度大於 O(log(m + n))，顯然不是最優的。

2.那如果不是直接使用二分查找算法，而是借用二分查找的思想呢？就是每次有選擇地捨棄掉數組的一部分，從而達到收斂數組縮小查找範圍的效果。

i.我們重新看題目，要找中位數，就是要找第 k 大的數（k = (L / 2 + 1)

其中L 是上面提到的合併後新數組的長度，當 L 是偶數時，要求第 (L / 2) 大和第 (L / 2 + 1) 大的兩個數）。

當我們捨棄掉一部分，假設捨棄部分的長度為 length，那麼接下來就是在剩下的數組裡求第 (k - length) 大的數。逐層縮小範圍，直到兩數組其中一個走完，或者要求的是第 1 大的元素，就可以直接返回結果了。

ii.那如何「選擇」要捨棄哪部分呢？

既然是要找合併後的數組 C 的第 k 大元素，即 C[k-1]，那如果我們從 A 和 B 中分別取前 k/2 個元素，其中必然有一部分是是在數組 C 的前 k 個數裡。

設 mid = k / 2，當 A[mid - 1] < B[mid - 1] 時，可以斷定 A 的前 mid 個元素是在 C 的前 k 個數裡（此處可用反證法得證），那麼我們則捨棄 A 的前 mid 個元素。反之則捨棄 B 的前 mid 個元素。

現在數組 A 或者 B 已經捨棄掉 k/2 個元素，縮小查找範圍了，那接下來可以按照同樣的方法繼續選擇嗎？當然！現在剩下總共 (L - mid) 個元素，且 A 和 B 依舊有序，要找的是第 (k - mid) 大的元素，所以我們可以按照上面的方法繼續遞歸選擇下去，直到找到目標元素！代碼如下：

參考程序

class Solution:
    """
    @param A: An integer array.
    @param B: An integer array.
    @return: a double whose format is *.5 or *.0
    """
    def findMedianSortedArrays(self, A, B):
        m, n = len(A), len(B)
        if m == 0 and n == 0:
            return 0.0

        total = m + n
        if total % 2 == 1:
            return self.kth_largest(A, B, total / 2 + 1) * 1.0
        else:
            a = self.kth_largest(A, B, total / 2)
            b = self.kth_largest(A, B, total / 2 + 1)
            return (a + b) / 2.0

    def kth_largest(self, A, B, kth):
        m, n = len(A), len(B)
        if m == 0:
            return B[kth-1]
        if n == 0:
            return A[kth-1]
        if kth == 1:
            return min(A[0], B[0])

        mid = kth / 2
        a, b = float("inf"), float("inf")
        if m >= mid:
            a = A[mid - 1]
        if n >= mid:
            b = B[mid - 1]
        if a < b:
            return self.kth_largest(A[mid:], B, kth - mid)
        else:
            return self.kth_largest(A, B[mid:], kth - mid)

複雜度分析：每次從合併後數組 C 裡減少 k/2 個元素，直到找到目標元素。所以時間複雜度是 O(log L) = O(log (m + n)) ！

面試官角度分析

這道題是二分方法的拓展運用，並且需要對二分有比較高的理解，比如怎麼樣通過猜測試一試二分來解決問題。如果能夠達到二分的方法，當然必然是Strong Hire的等級。

相關題目

可掃描下列二維碼直接進入

若有其他問題可留言後臺