LeetCode（Python3）4.寻找两个正序数组的中位数

Question：

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example1：

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example2：

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Mentality：

• 这道题的思路实质上很简单，只要将两个数组合为一个数据，然后返回中位数即可。虽然我觉得这样的效果很慢，但是效率却不低。
• 第二种种思路就是通过二分来切分两个数组，为了降低时间复杂度，选择长度小的数组进行切分，找到中位数后用该数切分另一个数组。如果nums1[midA]>nums2[minB-1]，则说明minA这条划分出的线应该向右移，以此类推，经过多次调整，总能找到中位数。

Code：

这边只给出简单思路的代码

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        length = len(nums1) + len(nums2)
        res = []
        while nums1 and nums2:
            res.append(nums1.pop(0) if nums1[0] < nums2[0] else nums2.pop(0))
        if nums1:
            res += nums1
        else:
            res += nums2
        if length % 2 == 0:
            return (res[length // 2 - 1] + res[length // 2]) / 2
        else:
            return res[length // 2] * 1

 Result：

发现这个代码时间不够快，于是想着学习前面的优秀代码。结果发现思路都和我这个差不多，我猜想可能是因为Python内置函数的封装比较高效，所以时间会比我快。

---

Optimized Code：

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums1.extend(nums2)
        res = sorted(nums1)
        if len(res) % 2 == 0:
            mid_index = len(res) // 2 - 1
            mid_value = (res[mid_index] + res[mid_index + 1]) / 2
        else:
            mid_index = len(res) // 2
            mid_value = res[mid_index]
        return mid_value

Result：

 果然，确实速度提高了许多。