4. Median of Two Sorted Arrays

Loading...LeetCode

题目要求 O(log(m+n)) 但其实直接暴力解法也能submit，不过这样就不是hard题了...

merge sort 也可以做，但还是要 O(m+n)，也不够。但从 merge sort 可以想到：最终排序好的 merged array 中，median 左边有一部分是nums1(A)贡献的，一部分是nums2(B)贡献的，右边同理。本质上，如果我们知道A贡献了多少元素给左边，多少给右边，然后就可以确定 merged array median的位置，所以关键问题就变成了在A中找到这个左右分割线。

在sorted array中找某个满足特定大小关系的位置，很容易就想到 binary search，但还有一个关键是，这个位置要符合什么样的条件？

先整体上看，A, B中有两个分割位置，这两个位置左边的数字，全体必须都小于右边的数字。也就是max(leftA, leftB) < min(rightA, rightB)，因为A,B本身都是sorted，所以leftA<rightA是肯定的，这个关系就可以被简化为：leftA<rightB, leftB<rightA

这样的话，这题思路就变成了较短的A做binary search，找到符合要求的分割位置。

（Median加上二分法，这题的边界 index 处理太太太太太太烦了...）

Brute Force

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

Binary Search

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        A, B = nums1, nums2
        if len(A) > len(B): return self.findMedianSortedArrays(nums2, nums1)
        
        lenMerge = len(A) + len(B)
        startA, endA = 0, len(A)
        
        while startA <= endA:
            cutA = (startA + endA) // 2
            cutB = (len(A) + len(B) + 1) // 2 - cutA
            lA = A[cutA - 1] if cutA != 0 else float('-inf')
            lB = B[cutB - 1] if cutB != 0 else float('-inf')
            rA = A[cutA] if cutA != len(A) else float('inf')
            rB = B[cutB] if cutB != len(B) else float('inf')
            if lA > rB: endA = cutA - 1
            elif lB > rA: startA = cutA + 1
            else:
                isEven = lenMerge % 2 == 0
                if isEven:
                    return (max(lA, lB) + min(rA, rB))/2
                else:
                    return max(lA, lB)

reference: