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

直接读的思路，时间复杂度没有满足题目中的log(m+n)，待优化

class Solution:
    def read(self, a, b):
        # 从两个数组中读出来一个较小的数字，然后删除原始数组中的数字
        if not a:
            r = b[0]
            del b[0]
        elif not b:
            r = a[0]
            del a[0]
        elif a[0] < b[0]:
            r = a[0]
            del a[0]
        else:
            r = b[0]
            del b[0]
        return r

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        total_len = len(nums1) + len(nums2)
        n = 0
        if total_len % 2 == 0:
            n = total_len // 2 - 1
        else:
            n = total_len // 2
        for i in range(n):
            self.read(nums1, nums2)
        r = 0
        if total_len % 2 == 0:
            for i in range(2):
                r += self.read(nums1, nums2)
            return r / 2
        else:
            return self.read(nums1, nums2)

评论