TikTok 两个有序数组第 k 大：分割边界与重复排名

题意与假设

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

• 训练数组非递减且支持随机访问，重复元素各算一位，k 从1开始。
• 代码返回第 r 小，调用 r=len(a)+len(b)-k；代码不预扫描排序以维持对数合同。

解题路线

1. 设取 A 前 i 项、B 前 j 项构成左半，i+j=r。i 只能在 max(0,r-lenB)..min(r,lenA) 范围。
2. 要让左侧恰为最小 r 项，需 A左最大≤B右最小且B左最大≤A右最小。缺失一侧边界单独处理，不访问越界项。
3. 若 A左大于B右，i 过大向左；若 B左大于A右，i 过小向右。满足时返回左侧最大。
4. 第 k 大不是去重后第 k 大；如果要 distinct 排名，不能简单沿用分割数量。

手动走一遍

A=[1,3,3]、B=[2,5]，第2大为3，对应第4小；第1大5、第5大1。一数组空时由另一数组边界直接回答，k=0 或>N拒绝。

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")

复杂度

O(log(min(m,n)+1)) 时间，O(1) 工作空间；排序验证若另做需 O(m+n)，不包含在已排序合同中。

易错点与追问

容易失分的边界

• k 大与 k 小没有转换。
• 把重复值排除。
• 分割边界使用无限哨兵破坏非数值类型。

继续深挖

• 无法随机访问时如何做 k 路合并？
• 想求中位数如何处理偶数？