LeetCode 补充题 193. 两个等长有序数组的上中位数

2026-09-14 HGNULB 约 5 分钟

文章信息 2 个分类 1 个标签

分类

补充题困难

题目描述

[!green]

牛客原题： ✅ 补充题 193. 两个等长有序数组的上中位数

给定两个长度均为 n 的非降序数组 nums1、nums2，返回合并后第 n 小的元素，即上中位数。

示例 1：

输入： nums1 = [1,3], nums2 = [2,4]
输出： 2

提示：

n >= 1
元素为 32 位整数。
不修改输入。

题意分析

合并后的上中位数是第 n 小，不需要真正合并两个数组。利用两段输入各自有序的性质，反复排除较小的一段前缀，并同步调整目标在剩余元素中的排名。

解法：二分淘汰前缀

核心思路

[!blue]

两个长度为 n 的数组合并后共有 2n 个数，上中位数是第 n 小，所以先把目标秩 k 设为 n；不是取中间两个数的平均值。

index1、index2 指向两数组尚未排除的后缀起点，k 是这些剩余元素中的目标排名。每轮各取至多 k/2 个元素比较前缀末值，排除较小末值所在的那一段，并从 k 中减去实际排除数。数组剩余长度不足 k/2 时，只能排除真实存在的元素。

较小末值所在前缀中的元素，不大于另一前缀末值；两段比较前缀的总长度不超过 k，因此可以移除较小前缀，并把目标秩减去它的长度。相等值可能对应多个相同排名值，移除其中部分出现次数不影响调整后目标的值。

k 降到 1 时直接取两个当前首值的较小者；一侧耗尽时，到另一侧按剩余秩取值。例如 [1,3] 和 [2,4] 求第 2 小，先排除 1，再在 3 和 2 之间取较小值，结果为 2。

解题步骤

两个起点设为 0，剩余目标排名 k 设为 n。

某侧耗尽时，直接返回另一侧起点后第 k 个元素；k 为 1 时返回两个首值的较小者。

各取至多 k/2 个元素，比较两段末值，排除末值较小的那段。

前移对应起点，从 k 中减去实际排除数，继续处理。

代码实现

class Solution {
    public int upperMedian(int[] nums1, int[] nums2) {
        int k = nums1.length;
        int index1 = 0;
        int index2 = 0;

        while (true) {
            if (index1 == nums1.length) {
                return nums2[index2 + k - 1];
            }

            if (index2 == nums2.length) {
                return nums1[index1 + k - 1];
            }

            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }

            int half = k / 2;
            int step1 = Math.min(half, nums1.length - index1);
            int step2 = Math.min(half, nums2.length - index2);
            int candidate1 = nums1[index1 + step1 - 1];
            int candidate2 = nums2[index2 + step2 - 1];

            if (candidate1 <= candidate2) {
                index1 += step1;
                k -= step1;
            } else {
                index2 += step2;
                k -= step2;
            }
        }
    }
}

func upperMedian(nums1 []int, nums2 []int) int {
    k := len(nums1)
    index1, index2 := 0, 0

    for {
        if index1 == len(nums1) {
            return nums2[index2+k-1]
        }
        if index2 == len(nums2) {
            return nums1[index1+k-1]
        }
        if k == 1 {
            if nums1[index1] < nums2[index2] {
                return nums1[index1]
            }
            return nums2[index2]
        }

        half := k / 2
        step1 := half
        if remain := len(nums1) - index1; step1 > remain {
            step1 = remain
        }
        step2 := half
        if remain := len(nums2) - index2; step2 > remain {
            step2 = remain
        }

        candidate1 := nums1[index1+step1-1]
        candidate2 := nums2[index2+step2-1]
        if candidate1 <= candidate2 {
            index1 += step1
            k -= step1
        } else {
            index2 += step2
            k -= step2
        }
    }
}

复杂度分析

时间复杂度：$O(\log n)$。

空间复杂度：额外空间 $O(1)$。

关键点总结

[!green]

把目标秩设置为 n，再每轮比较两个候选前缀的末项，淘汰不可能包含目标的较小前缀，同时扣减目标秩。

易错点总结

[!yellow]

上中位数取第 n 小，不是第 n+1 小，也不求两项平均值。

k 是剩余部分的排名，每次必须减去实际排除的元素数。

先处理耗尽和 k=1，避免取到空前缀或越界。

相同值允许存在；排除部分相等元素后，目标值仍由调整后的排名确定。

相似题目

题目	难度	关联与区别
补充题 17. 两个有序数组第 k 小的数	困难	两题都查询两个有序数组合并后的指定名次；本题限定数组等长，目标为第 n 小，可直接复用该题的第 k 小查询。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/80628881038

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！