关于算法:Leetcode-04-Median-of-Two-Sorted-Arrays

[4] Median of Two Sorted Arrays

Difficulty: Hard (33.87%)

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)).

example:

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

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.

为了解决这个问题, 首先咱们将其合成为两个字问题

1. 如何求两个数组中第 k 个数
2. 如何计算中位数

如何求两个数组中第 k 个数

因为两个数组都是有序数组, 且题目要求咱们达到 log(m+n)的工夫复杂度, 所以应该尝试利用有序的个性, 应用二分的办法来解决这个问题

完结条件

如果一个数组空了, 两个数组的第 k 个数则为非空数组的第 k 个数

递归条件

如果两个数组均非空, 找到两个数组两头的数
如果 k 在 i1 和 i2 的右侧, 找出更小的那个, 截取后半段.
如果 k 在 i1 和 i2 的左侧, 找出更大的那个, 截取前半段.

def kth(l1, l2, k):
    if not l1:
        return l2[k]
    if not l2:
        return l1[k]
    i1 = len(l1) // 2
    i2 = len(l2) // 2
    # 如果 k 在 i1、i2 的右侧
    if i1 + i2 < k:
        # 找出更小的那个，截取后半段
        if l1[i1] < l2[i2]:
            return kth(l1[i1 + 1:], l2, k - i1 - 1)
        else:
            return kth(l1, l2[i2 + 1:], k - i2 - 1)
    else:
        # k 在 i1、i2 的左侧，找出更大的那个，截取前半段
        if l1[i1] < l2[i2]:
            return kth(l1, l2[:i2], k)
        else:
            return kth(l1[:i1], l2, k)

如何计算中位数

如果数组为复数个元素, 找到第 (m+n)// 2 个数
如果数组为单数个元素, 找到第(m+n)// 2 个数和第(m+n)//2 – 1 个数, 求均匀即可

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)
        if (m + n) % 2 == 1:
            return self.kth(nums1, nums2, (m + n) // 2)
        else:
            return (self.kth(nums1, nums2, (m + n) // 2) + self.kth(nums1, nums2, (m + n) // 2 - 1)
            ) / 2.0