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

Categories:

Tags:

题目描述
思路分析
1. 解法一：二分查找（转化为求第 k 小）（推荐）
相似题目

题目描述

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

思路分析

解法一：二分查找（转化为求第 k 小）（推荐）

核心思路：

题目要求时间复杂度 O(log(m+n))，不能合并后排序（那是 O(m+n)）。

转化：中位数等价于求合并后有序数组的第 k 小（或第 k 和第 k+1 小的均值）：

总长奇数：取第 (m+n+1)/2 小

总长偶数：取第 (m+n)/2 和第 (m+n)/2 + 1 小的均值

getKth(nums1, nums2, s1, s2, k) 的核心思路：

每次比较两个数组从当前起点 s1, s2 各自的第 k/2 个元素（下标 idx1 = s1 + k/2 - 1，idx2 = s2 + k/2 - 1）：

若 nums1[idx1] <= nums2[idx2]：nums1[s1..idx1] 这 k/2 个元素都不可能是第 k 小（因为右边比它大的元素至少有 k/2 个），可以安全排除，起点移到 idx1 + 1，k 减少 idx1 - s1 + 1

反之排除 nums2 的前缀

边界：某数组耗尽时直接返回另一个数组的对应元素；k == 1 时返回两个起点中较小者

注意：若剩余长度 < k/2，取到末尾（idx = min(s + k/2 - 1, len - 1)），实际排除数量可能少于 k/2，需正确更新 k

每次递归排除约 k/2 个元素，k 减半，共 O(log k) 次，整体 O(log(m+n))。

复杂度分析：

时间复杂度：O(log(m+n))，其中 m、n 分别表示两个数组的长度，每次递归将问题规模减半

空间复杂度：O(log(m+n))，其中递归栈深度为 log(m+n)

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int total = nums1.length + nums2.length;
        // 奇数取中间一个，偶数取中间两个的均值
        if (total % 2 == 1) {
            return getKth(nums1, nums2, 0, 0, total / 2 + 1);
        }
        return (getKth(nums1, nums2, 0, 0, total / 2) + getKth(nums1, nums2, 0, 0, total / 2 + 1)) / 2.0;
    }

    private int getKth(int[] nums1, int[] nums2, int s1, int s2, int k) {
        // 某数组已耗尽，直接取另一个数组的第 k 个
        if (s1 >= nums1.length) {
            return nums2[s2 + k - 1];
        }
        if (s2 >= nums2.length) {
            return nums1[s1 + k - 1];
        }
        // k == 1 时返回两个起点中的较小值
        if (k == 1) {
            return Math.min(nums1[s1], nums2[s2]);
        }
        int half = k / 2;
        // 防止数组越界，取到末尾
        int idx1 = Math.min(s1 + half - 1, nums1.length - 1);
        int idx2 = Math.min(s2 + half - 1, nums2.length - 1);
        // 排除较小一侧的前缀，同时正确更新 k
        if (nums1[idx1] <= nums2[idx2]) {
            return getKth(nums1, nums2, idx1 + 1, s2, k - (idx1 - s1 + 1));
        }
        return getKth(nums1, nums2, s1, idx2 + 1, k - (idx2 - s2 + 1));
    }
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    m, n := len(nums1), len(nums2)
    total := m + n
    // 奇数取中间一个，偶数取中间两个的均值
    if total%2 == 1 {
        return float64(getKth(nums1, nums2, 0, 0, total/2+1))
    }
    return float64(getKth(nums1, nums2, 0, 0, total/2)+getKth(nums1, nums2, 0, 0, total/2+1)) / 2.0
}

func getKth(nums1, nums2 []int, start1, start2, k int) int {
    // 某数组已耗尽，直接取另一个数组的第 k 个
    if start1 >= len(nums1) {
        return nums2[start2+k-1]
    }
    if start2 >= len(nums2) {
        return nums1[start1+k-1]
    }
    // k == 1 时返回两个起点中的较小值
    if k == 1 {
        if nums1[start1] < nums2[start2] {
            return nums1[start1]
        }
        return nums2[start2]
    }
    half := k / 2
    // 防止数组越界，取到末尾
    idx1 := min4(start1+half-1, len(nums1)-1)
    idx2 := min4(start2+half-1, len(nums2)-1)
    // 排除较小一侧的前缀，同时正确更新 k
    if nums1[idx1] <= nums2[idx2] {
        return getKth(nums1, nums2, idx1+1, start2, k-(idx1-start1+1))
    }
    return getKth(nums1, nums2, start1, idx2+1, k-(idx2-start2+1))
}

func min4(a, b int) int {
    if a < b {
        return a
    }
    return b
}

相似题目

题目	难度	考察点
295. 数据流的中位数	困难	堆
378. 有序矩阵中第 K 小的元素	中等	二分查找
668. 乘法表中第k小的数	困难	二分查找
23. 合并 K 个升序链表	困难	多路归并
215. 数组中的第K个最大元素	中等	快速选择
410. 分割数组的最大值	困难	二分查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/26276715