4. Median of Two Sorted Arrays

2019-03-28

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)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums = [0] * (len(nums1) + len(nums2))  # 合并列表
        i, j, k = 0, 0, 0
        while k < len(nums):    # 循环合并
            if i >= len(nums1): # 如果只剩列表2
                nums[k] = nums2[j]  # 添加列表2的元素
                j += 1
            elif j >= len(nums2):   # 如果只剩列表1的元素
                nums[k] = nums1[i]  # 添加列表1的元素
                i += 1
            else:   # 如果两列表都存在
                if nums1[i] < nums2[j]: # 取两列表头部较小值
                    nums[k] = nums1[i]
                    i += 1
                else:
                    nums[k] = nums2[j]
                    j += 1
            k += 1  # 移动合并后列表的游标
        if len(nums) % 2 == 1:  # 如果合并后的列表奇数个元素
            n = int((len(nums)-1)/2)
            m = nums[n]
        else:   # 偶数个
            mi = nums[int(len(nums) / 2 - 1)]
            ma = nums[int(len(nums) / 2)]
            m = (mi+ma)/2
        return m

# 如果新列表数是4的话，那么平均值为(nums[1]+nums[2])/2   从零开始计数
-->