4. 寻找两个正序数组的中位数 Python-Leetcode

📕题干

困难

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

📖题解

· 法一

💻代码

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        all = nums1 + nums2
        all.sort()
        a = len(all)//2
        if len(all)%2 == 1:
            return all[a]
        else:
            return (all[a-1]+all[a])/2

执行用时：44ms 消耗内存：16.64MB

🤔思路

直接暴力求解，对两个数列合并，sort()排序，然后二分求中位数。

❗ 注意

虽然过程直接了当，但是题干要求的时间复杂度是_O_(Log(m+n))，很显然，此时代码的时间复杂度是_O(NLogn)_，所以说需要进一步优化算法。

· 法二

💻代码

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m,n = len(nums1),len(nums2)
        result = []
        i,j = 0,0
        while len(result) <= (m+n)/2:
            if i == len(nums1):
                while len(result) <= (m+n)/2:
                    result += [nums2[j]]
                    j += 1
            elif j == len(nums2):
                while len(result) <= (m+n)/2:
                    result += [nums1[i]]
                    i += 1
            else:
                if nums1[i] <= nums2[j]:
                    result += [nums1[i]]
                    i += 1

                else:
                    nums1,nums2 = nums2,nums1
                    i,j = j,i
                    m,n = n,m
        if (m+n)%2 == 1:
            return result[-1]
        else:
            return (result[-1]+result[-2])/2

执行用时：38ms 消耗内存：16.64MB

🤔思路

由于法一是运用了sort()才会有_O(NLogn)的时间复杂度，所以我在法二中避免了运用sort()。换种方式思考，能发现由于两个列表都是正序排列，我们可以逐一从开头取出较小的数塞进result中，当result中的数达到或者超过了一半时，便可以快速的算出中位数了，此时的运算结果时间复杂度便降到了_O(Log min(m,n)),比题干要求还小。