一、题目

Median of Two Sorted Arrays

二、解题

1）题意

给出两个已经排好序的有序数组，求出两个数组的中间值（如果有两个值，则求两个数的平均值）

2）关键点

题目本身不难，难在时间复杂度的要求，需要达到O(log(m＋n))

三、思考：

1）如果抛去时间复杂度的要求，这题的思路便比较明晰。

• 首先进行二路归并
• 求得中位数

四、尝试与结果

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;

结果：AC（此算法的时间复杂度为O(m+n)）