LeetCode 补充题 17. 两个有序数组第k小的数

2025-05-23 HGNULB 约 6 分钟

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

分类

LeetCode CodeTop 困难未解决 5-10 字节跳动微软腾讯拼多多高频面试题

题目描述

✅ 补充题 17. 两个有序数组第k小的数

题意分析

给定两个各自已经升序排好的数组，要返回把它们合在一起后按升序排列的第 $k$ 个元素。排名从 $1$ 开始数，即 $k = 1$ 时要的是全局最小值。

注意合并是「多重集合」意义上的：两个数组里相等的元素各算一份，不去重。所以第 $k$ 小指的是允许重复的排名，而不是第 $k$ 个不同的值。

「已经有序」是本题唯一的可利用条件，也是全部题眼。若无视它直接归并到第 $k$ 个为止，代价是 $O(k)$，最坏是 $O(m + n)$；面试问这道题就是想看能不能把这个线性代价降下来。

边界情形有几类：某个数组为空，答案完全落在另一个数组里；$k$ 等于 $1$，答案是两个首元素的较小者；$k$ 等于两数组长度之和，答案是全局最大值；两个数组元素大量相等，此时任何比较规则都必须保证至少能推进一步，否则会卡死；以及某个数组的剩余长度不足以提供想要的候选个数。这里假定调用方给出的 $k$ 落在 $1$ 到两数组长度之和的范围内。

解法：每轮淘汰约一半候选

核心思路

维护两个数组尚未淘汰的起点，以及当前要找的排名 k。当 k > 1 时，分别查看两个后缀中第 k / 2 个候选；若某个后缀不够长，就只取到末尾。

若第一个候选值不大于第二个，那么第一个数组候选点之前的元素都不可能是当前第 k 小，可以整段淘汰。直观上，这一段至多只占合并后前 k - 1 个位置；候选值相等时，即使答案值就在这里，另一个数组仍保留着相同值，所以淘汰一侧仍安全。

循环不变量是：原问题的答案，始终等于“两个当前后缀合并后的第 k 小”。淘汰 step 个元素时，数组起点前移 step，同时令 k -= step，不变量继续成立。

两个出口也很重要：某个后缀为空时，直接在另一个数组中按排名取值；k == 1 时，答案是两个后缀首元素的较小值。

解题步骤

令两个起点都为 0。

若某个数组已经耗尽，返回另一个数组中下标 start + k - 1 的元素。

若 k == 1，返回两个当前首元素的较小值。

取 half = k / 2，两侧步长均不能超过各自剩余长度。

比较两段前缀的末元素，淘汰末元素较小的一段，并同步减少 k。

重复以上过程，直到命中出口。

例如 [1,3,5] 与 [2,4,6] 中找第 4 小：先比较 3 和 4，淘汰 [1,3]，问题变成 [5] 与 [2,4,6] 中找第 2 小；再淘汰 2，最终比较 5 和 4，得到 4。

代码实现

class Solution {
    public int findKth(int[] nums1, int[] nums2, int k) {
        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 findKth(nums1 []int, nums2 []int, k int) int {
    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 k)$。通常每轮淘汰约 k / 2 个元素；若某侧不足一半，它会很快耗尽并直接返回。

空间复杂度：$O(1)$，迭代过程只维护下标和临时变量。

关键点总结

有序性让一次比较可以排除整段前缀，而不必逐个归并。

起点与 k 必须同步更新，才能维持“当前后缀中的第 k 小”这一状态定义。

步长要受剩余长度限制，否则候选下标会越界。

k == 1 必须提前处理，否则 k / 2 == 0，循环无法推进。

两数组中相同的元素各自占一个排名，不能去重。

易错点总结

把 k 当成从零开始的下标：耗尽分支应取 start + k - 1。

比较每段的首元素而不是末元素：无法证明整段都能淘汰。

淘汰后只移动起点、不减少 k：目标排名会整体偏后。

候选相等时同时淘汰两侧：可能一次删掉至少 k 个元素，越过答案。

未约定参数合法性：本实现依赖 1 <= k <= len(nums1) + len(nums2)。

相似题目

题目	难度	考察点
4. 寻找两个正序数组的中位数	困难	把本题当子过程调用一到两次，额外要处理总长度奇偶带来的取值差异
215. 数组中的第K个最大元素	中等	输入无序，只能靠快速选择或堆，无法利用有序性做整段淘汰
378. 有序矩阵中第 K 小的元素	中等	有序结构升到二维，通常对答案值域二分并统计不超过它的个数
668. 乘法表中第k小的数	困难	数据由公式隐式给出，不能落地成数组，只能对值域二分
719. 找出第 K 小的数对距离	困难	候选是所有点对的差值，需排序后用双指针配合值域二分统计
373. 查找和最小的 K 对数字	中等	要输出前 $k$ 个组合而非单个排名，靠最小堆逐步扩展候选
23. 合并 K 个升序链表	困难	从两路推广到多路且要求完整输出，无法整段淘汰，只能堆或分治归并