4. Median of Two Sorted Arrays-白红宇

4. Median of Two Sorted Arrays

阅读量：796 次

发布时间：2023-03-23

本文共 1115 字，大约阅读时间需要 3 分钟。

以下是如何高效找到两个已排序数组的中位数的详细步骤：

要找到两个已排序数组的中位数，时间复杂度应为O(log(m+n))。中位数的定义取决于两个数组的总长度：

当总长度为奇数时，中位数为中间的那个数。

当总长度为偶数时，中位数为中间两个数的平均值。

为了高效找到中位数，我们可以使用双指针法。以下是具体步骤：

计算两个数组的总长度，并确定中位数的位置k：

总长度为odd时，k = (m + n) // 2。

总长度为even时，k = (m + n) // 2。

定义一个辅助函数find_kth(nums1, nums2, k)，返回第k个最小的数：

初始化两个指针i和j分别指向nums1和nums2的开头。

在循环中，比较nums1[i]和nums2[j]，选择较小的数作为当前最小值，并移动相应的指针。

当count等于k时，返回当前最小值。

根据总长度的奇偶性：

如果总长度为奇数，找到第k+1个最小的数作为中位数。

如果总长度为偶数，找到第k和第k+1个最小的数，并计算它们的平均值。

代码实现如下：

def find_median(nums1, nums2):
    m = len(nums1)
    n = len(nums2)
    total = m + n
    k = total // 2
    def find_kth(nums1, nums2, k):
        i = j = 0
        count = 0
        current = 0
        while count < k:
            if nums1[i] <= nums2[j]:
                current = nums1[i]
                i += 1
            else:
                current = nums2[j]
                j += 1
            count += 1
        return current
    if total % 2 == 1:
        return find_kth(nums1, nums2, k + 1)
    else:
        a = find_kth(nums1, nums2, k + 1)
        b = find_kth(nums1, nums2, k)
        return (a + b) / 2