4. Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/

solution

• merge sort

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        res = []
        i = j = 0
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                res.append(nums1[i])
                i += 1
            else:
                res.append(nums2[j])
                j += 1
        if i < len(nums1):
            res += nums1[i:]
        elif j < len(nums2):
            res += nums2[j:]

        if len(res) % 2 == 1:
            return res[(len(res) - 1) // 2]
        else:
            return (res[len(res) // 2] + res[len(res) // 2 - 1]) / 2

时间复杂度：O() 空间复杂度：O()

• 二分查找

  • 找中位数是find kth largest element的特殊情况

  • 将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。

  • 第一个数组a，第二个数组b，如果确认中位数在第一个数组的 [l,r] 之间或者在第二个数组的 [L,R] 之间，记 mid1=(l+r)/2,mid2=(L+R)/2，这会将 [l,r] 和 [L,R] 分成四个区间，比较 a[mid1] 和 b[mid2] 可以得到哪个区间中一定没有中位数，然后对应把 l,r,L,R 中的某一个修改成 mid1 或者 mid2。这样每次待定的区间长度会减少四分之一，复杂度为 logN

# 示意图from: https://www.geeksforgeeks.org/median-of-two-sorted-arrays/?ref=lbp
# https://www.geeksforgeeks.org/median-of-two-sorted-arrays-of-different-sizes/

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        n1 = len(nums1)
        n2 = len(nums2)

        if n1 > n2:
            return self.findMedianSortedArrays(nums2, nums1)

        left = (n1 + n2 + 1) // 2  # Calculate the left partition size
        low = 0
        high = n1

        while low <= high:
            mid1 = (low + high) // 2  # Calculate mid index for nums1
            mid2 = left - mid1  # Calculate mid index for nums2

            l1 = float('-inf')
            l2 = float('-inf')
            r1 = float('inf')
            r2 = float('inf')

            # Determine values of l1, l2, r1, and r2
            if mid1 < n1:
                r1 = nums1[mid1]
            if mid2 < n2:
                r2 = nums2[mid2]
            if mid1 >= 1:
                l1 = nums1[mid1 - 1]
            if mid2 >= 1:
                l2 = nums2[mid2 - 1]

            if l1 <= r2 and l2 <= r1:
                # The partition is correct, we found the median
                if (n1 + n2) % 2 == 1:
                    return max(l1, l2)
                else:
                    return (max(l1, l2) + min(r1, r2)) / 2.0
            elif l1 > r2:
                high = mid1 - 1
            else:
                low = mid1 + 1
        return 0

时间复杂度：O() 空间复杂度：O()

• heap

follow up

2040. Kth Smallest Product of Two Sorted Arrays