如何攻克陌生算法题：求两个有序数组合并的第k小元素（O(lg k)）

一、这道题的分治思路推导过程 #

你已经能写出O(k)的双指针解法，本质是每次移动指针排除1个不可能是答案的元素，要优化到O(lg k)的核心逻辑很简单：每次操作批量排除一批肯定不是答案的元素，而不是只排除1个，这也是所有线性复杂度优化到对数复杂度的通用思路，和你已经掌握的分治思想完全契合。

具体推导步骤：

• 目标是找第k小元素，我们可以先从两个数组各取前k//2个元素比较末尾值（注意取值不能超过数组本身长度）
• 假设A数组取了i = min(len(A), k//2)个，B数组取了j = min(len(B), k//2)个
  • 如果A[i-1] < B[j-1]：A的前i个元素就算全部排在B的前j个元素前面，加起来最多也才i+j ≤ k个，所以A的前i个元素肯定都在合并后的前k个元素里，直接扔掉这部分，问题缩小为：从剩余的A[i:]和完整B数组中找第k-i小的元素，k直接缩小了至少一半
  • 如果B[j-1] < A[i-1]：同理扔掉B的前j个元素，问题缩小为找第k-j小的元素
• 边界情况处理：如果其中一个数组为空，直接返回另一个数组的第k-1个元素；如果k=1，直接返回两个数组首元素的较小值

整个过程k每次减半，自然能达到O(lg k)的时间复杂度，完全是从基础解法逐步优化来的，不是凭空出现的技巧。

二、陌生高效算法的通用设计思路 #

不用默认必须刷大量题才能解出陌生题，可以按这个固定路径推导：

• 先写出你能想到的最基础的可行解法，明确这个解法的效率瓶颈在哪里，比如这道题的O(k)解法瓶颈就是每次只能排除1个元素
• 对照题目要求的复杂度目标找优化方向：如果要求对数复杂度，就往「每次能排除固定比例的候选元素」的方向想；如果要求线性复杂度，就往「每个元素只遍历一次」的方向想
• 分治类问题不用先回忆类似题型，先想「怎么把当前问题规模缩小一半」，这道题里k就是核心问题规模，每次把k减半自然就能达到要求的复杂度

三、关于刷题的误区 #

题量积累有帮助，但绝不是唯一路径。你做完每道题不用死记具体解法，而是记「这类问题的通用优化方向」：比如有序数组找特定值的优化方向是二分批量缩小范围，子串类问题的优化方向是滑动窗口避免重复计算。碰到新题先往你总结过的优化方向上靠，比背几百道题的解法效率高得多。

参考实现（Python） #

def find_kth_smallest(A, B, k):
    # 保证A是较短数组，减少边界判断
    if len(A) > len(B):
        return find_kth_smallest(B, A, k)
    # 边界1：A数组为空，直接返回B的第k-1个元素
    if len(A) == 0:
        return B[k-1]
    # 边界2：k=1，直接返回两数组首元素较小值
    if k == 1:
        return min(A[0], B[0])
    # 各取k//2个元素，不超过数组长度
    i = min(len(A), k//2)
    j = min(len(B), k//2)
    if A[i-1] < B[j-1]:
        # 扔掉A的前i个元素，递归找第k-i小
        return find_kth_smallest(A[i:], B, k - i)
    else:
        # 扔掉B的前j个元素，递归找第k-j小
        return find_kth_smallest(A, B[j:], k - j)

内容的提问来源于stack exchange，提问作者Lurgypai