一、題目

Median of Two Sorted Arrays

二、解題

1）題意

給出兩個已經(jīng)排好序的有序數(shù)組，求出兩個數(shù)組的中間值（如果有兩個值，則求兩個數(shù)的平均值）

2）關(guān)鍵點

題目本身不難，難在時間復雜度的要求，需要達到O(log(m＋n))

三、思考：

1）如果拋去時間復雜度的要求，這題的思路便比較明晰。

• 首先進行二路歸并
• 求得中位數(shù)

四、嘗試與結(jié)果

1）時間復雜度O(m+n)

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        i = 0
        j = 0
        numList = []
        result = -1
        while i < len(nums1) and j < len(nums2):
            if (nums1[i] < nums2[j]):
                numList.append(nums1[i])
                i += 1
            else:
                numList.append(nums2[j])
                j += 1
        if ( i == len(nums1)):
            numList.extend(nums2[j:])
        else:
            numList.extend(nums1[i:])

        if (len(numList)%2==1):
            result = numList[len(numList)/2]
        else:
            result = (numList[len(numList)/2] + numList[len(numList)/2 - 1])/2.0
        return result;

結(jié)果：AC（此算法的時間復雜度為O(m+n)）