LeetCode 补充题 17. 两个有序数组第 k 小的数
题目描述
给定两个分别按非递减顺序排列的整数数组
nums1、nums2，以及合法排名k，请返回两个数组合并后的第k小元素。排名从
1开始。重复元素按出现次数分别计入排名，不是寻找第k个不同的值。
示例 1：
输入：nums1 = [1,3,5], nums2 = [2,4,6], k = 4
输出：4
示例 2：
输入：nums1 = [], nums2 = [2,2,5], k = 2
输出：2
提示：
- 两个数组都已按非递减顺序排列，可以包含重复值。
-
1 <= k <= nums1.length + nums2.length。 - 允许其中一个数组为空，不需要构造完整的合并数组。
题意分析
两个数组各自按升序排列，要求返回它们合并后的第
k小数值，排名从1开始。重复元素按出现次数分别占据排名，不是找第k个不同的数，也不是返回某个原数组下标。这里按合法排名处理，即
1 <= k <= 两数组长度之和。允许一侧为空，或两侧长度相差很大；无需真正创建完整的合并数组，只要定位目标排名。
解法：每轮淘汰约一半候选
核心思路
[!blue]
用
index1、index2表示两侧尚未排除的后缀起点，k表示目标在这两个剩余后缀中的排名。每次删除一批确定可以排在目标之前的元素，同时从k中扣除数量，就能保持寻找的数值不变。当
k > 1时，每侧先取至多k / 2个元素，数量分别为p、q，比较两段的最后一个值a、b。若a <= b，准备删除第一侧的这p个元素。为什么可以删？第一侧前
p个值都不大于a，它后面的值不小于a；第二侧从第q个值开始都不小于b，也就不小于a。因此把相等值中准备删除的这一段排在前面时，a的位置至多是p + q - 1，而它不超过2 × floor(k / 2) - 1 < k。整段都可以排在第k个出现之前，删除它后改找第k - p小，答案数值不变。a > b时对称删除第二侧。相等时也只删除一侧。被删元素的数值可能恰好等于答案，但另一侧仍保留对应的相同值，排名扣减后能够继续找到它；若同时删除两侧，就可能连目标所处的出现次数一起越过。
某侧耗尽后，直接在另一侧按剩余排名取值；
k = 1时，答案就是两侧首项的较小者。若没有直接结束，通常会删掉约一半排名；当选中前缀不足半数时，该侧会被直接耗尽，下一轮即可返回。
解题步骤
- 将两个后缀起点都初始化为
0。- 优先检查某侧是否耗尽；若耗尽，返回另一侧起点之后第
k - 1个偏移位置的值。- 两侧都非空且
k = 1时，返回两个首项的较小值。- 分别取
min(k / 2, 当前侧剩余长度)个候选元素，比较各自末项。- 删除末项较小的一侧前缀，相等时选第一侧；对应起点前移多少，排名就减去多少。
- 对缩小后的两个后缀重复，直到命中直接返回条件。
代码实现
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+1))$，每轮约减半或耗尽一侧。
- 空间复杂度：$O(1)$，后缀起点与排名。
关键点总结
[!green]
k始终是剩余集合中的排名，移动起点与扣减排名必须同步。- 一次删除整段依赖前缀末项比较和排名上界，不是只比较两个数后随意跳步。
- 相同数值可以占多个排名，删除部分相同值不会改变相应剩余排名的答案数值。
易错点总结
[!yellow]
- 直接访问第
k / 2个剩余元素，而不限制实际长度，会在较短数组中越界。- 忽略
k = 1，会算出零步长，既无法正确选候选，也无法推进循环。- 更新数组起点但不扣减排名，寻找的就变成原目标之后的元素。
- 候选相等时同时淘汰两侧，可能删除过多元素，越过目标排名。
- 一侧耗尽后直接把
k当数组下标，会遗漏当前起点以及排名从1开始的偏移。- 为了去重而合并相等值，会改变多重集合中的排名定义。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 4. 寻找两个正序数组的中位数 | 困难 | 中位数是合并后一个或两个特定名次，本题将查询推广到任意合法k，重复值仍分别计数。 |
| 补充题 193. 两个等长有序数组的上中位数 | 困难 | 该题限定两个数组等长，取合并后的第 n 小元素；本题允许长度不同，并将目标名次推广为任意合法 k。 |