Amazon Coding：两个有序数组的第 K 小，二分划分如何证明？

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• a/b升序、可随机访问，重复值按出现次数计数；k从1起，1≤k≤m+n。
• 不预扫描验证有序性，以免把对数算法变O(m+n)；调用方保证输入有序。真正linked list不支持O(1)下标，须用合并扫描。

解题路线

1. 短数组a划出i个，b划出j=k-i个，左侧正好k个。i范围[max(0,k-n),min(k,m)]确保两边容量合法。
2. 若a左末>b右首，i太大向左搜；若b左末>a右首，i太小向右搜。其他情况左半所有元素≤右半，第k小就是左边最大值。
3. 单调依据：增i使a左末不减，同时j减使b右首不增，因此第一种违规不会靠继续右移修复；第二种相反。合法划分可以多个，但第k值不变。
4. 边界不用float infinity冒充任意类型：只在对应端存在时比较。i=0直接取b[j-1]，j=0取a[i-1]；合法k保证不同时为0。
5. 若接口真是单链表，双指针弹出k个元素O(k)且O(1)空间更合适；不能把数组二分的复杂度直接承诺给链表。

手动走一遍

a=[1,3],b=[2,3,8],k=4，i=2,j=2，左端3/3，b右8，结果3。重复值都计数；a=[]、b=[7]、k=1返回7。105,840个合法排名与整体排序独立对照通过。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def kth_smallest(a, b, k):
    """Sorted random-access arrays; k is one-based, duplicates count separately."""
    if not 1 <= k <= len(a) + len(b):
        raise ValueError("invalid k")
    if len(a) > len(b):
        a, b = b, a
    lo, hi = max(0, k - len(b)), min(k, len(a))
    while lo <= hi:
        i = (lo + hi) // 2
        j = k - i
        if i > 0 and j < len(b) and a[i - 1] > b[j]:
            hi = i - 1
        elif j > 0 and i < len(a) and b[j - 1] > a[i]:
            lo = i + 1
        elif i == 0:
            return b[j - 1]
        elif j == 0:
            return a[i - 1]
        else:
            return max(a[i - 1], b[j - 1])
    raise ValueError("inputs violate sorted-order contract")

复杂度

二分区间最多min(m,k)+1个候选，O(log(min(m,n)+1))时间、O(1)辅助空间；空短数组直接常数返回。链表替代方案O(k)。

易错点与追问

容易失分的边界

• k误作零基。
• 把重复值去重。
• 二分长数组导致j越界。
• 链表下标当O(1)。

继续深挖

• 两个数组中位数怎样处理偶数长度？
• K个有序流用什么结构？
• 不允许随机访问怎么办？