Median of Two Sorted Arrays問題：求2個(gè)有序數(shù)組的中位數(shù)，要求算法時(shí)間復(fù)雜度為O(log(m+n))。

難度：困難

思路：此題為“在2個(gè)有序數(shù)組中尋找第k個(gè)元素”問題的變體。根據(jù)中位數(shù)的定義，此題可轉(zhuǎn)化為“在2個(gè)有序數(shù)組中尋找第‘(m+n)/2’個(gè)元素”。算法難點(diǎn)在于要求時(shí)間復(fù)雜度為O(log(m+n))，因此需要充分利用2個(gè)數(shù)組有序這一條件，每次循環(huán)將搜索空間縮小一半。

陷阱：數(shù)組下標(biāo)計(jì)算。另外由于LeetCode網(wǎng)站測試用例設(shè)置問題，線性時(shí)間復(fù)雜度的算法也可能被接受。

代碼：

class Solution:
    # @param {integer[]} nums1
    # @param {integer[]} nums2
    # @return {float}
    def find(self, nums1, nums2, k):
        if not nums1:
            return nums2[k]
        if not nums2:
            return nums1[k]
        ia, ib = len(nums1) // 2 , len(nums2) // 2
        ma, mb = nums1[ia], nums2[ib]
        if ia + ib < k:
            if ma > mb:
                return self.find(nums1, nums2[ib + 1:], k - ib - 1)
            else:
                return self.find(nums1[ia + 1:], nums2, k - ia - 1)
        else:
            if ma > mb:
                return self.find(nums1[:ia], nums2, k)
            else:
                return self.find(nums1, nums2[:ib], k)

    def findMedianSortedArrays(self, nums1, nums2):
        l = len(nums1) + len(nums2)
        if l % 2 == 1:
            return self.find(nums1, nums2, l // 2)
        else:
            return (self.find(nums1, nums2, l // 2) + self.find(nums1, nums2, l // 2 - 1)) / 2.0

另外，有人指出Python數(shù)組分片操作本身具有線性時(shí)間復(fù)雜度，因此嚴(yán)格地說上述算法不具備O(log(m+n))的時(shí)間復(fù)雜度。改進(jìn)方法是將數(shù)組起止下標(biāo)作為變量傳給find函數(shù)，代碼如下：

class Solution:
    # @param {integer[]} nums1
    # @param {integer[]} nums2
    # @return {float}
    def find(self, nums1, s1, e1, nums2, s2, e2, k):
        if e1 - s1 < 0:
            return nums2[k + s2]
        if e2 - s2 < 0:
            return nums1[k + s1]
        if k < 1:
            return min(nums1[k + s1], nums2[k + s2])
        ia, ib = (s1 + e1) // 2 , (s2 + e2) // 2
        ma, mb = nums1[ia], nums2[ib]
        if (ia - s1) + (ib - s2) < k:
            if ma > mb:
                return self.find(nums1, s1, e1, nums2, ib + 1, e2, k - (ib - s2) - 1)
            else:
                return self.find(nums1, ia + 1, e1, nums2, s2, e2, k - (ia - s1) - 1)
        else:
            if ma > mb:
                return self.find(nums1, s1, ia - 1, nums2, s2, e2, k)
            else:
                return self.find(nums1, s1, e1, nums2, s2, ib - 1, k)

    def findMedianSortedArrays(self, nums1, nums2):
        l = len(nums1) + len(nums2)
        if l % 2 == 1:
            return self.find(nums1, 0, len(nums1) - 1, nums2, 0, len(nums2) - 1, l // 2)
        else:
            return (self.find(nums1, 0, len(nums1) - 1, nums2, 0, len(nums2) - 1, l // 2) + self.find(nums1, 0, len(nums1) - 1, nums2, 0, len(nums2) - 1, l // 2 - 1)) / 2.0

附：線性時(shí)間復(fù)雜度算法代碼：

class Solution:
    # @param {integer[]} nums1
    # @param {integer[]} nums2
    # @return {float}
    def findMedianSortedArrays(self, nums1, nums2):
        mid = (len(nums1) + len(nums2) >> 1) + 1
        i = j = 0
        median = n = None
        for k in xrange(mid):
            v1 = nums1[i] if i < len(nums1) else None
            v2 = nums2[j] if j < len(nums2) else None
            n = median
            if v2 is None or (v1 is not None and v1 < v2):
                median = v1
                i += 1
            else:
                median = v2
                j += 1
        if (len(nums1) + len(nums2)) % 2 == 0 and n is not None:
            return (median + n) / 2.0
        return median