如何用递归在未排序数组中找第K小元素？我的代码有何问题？

你的代码存在三个核心问题，导致无法正确找到第K小元素：

• 条件判断逻辑错误：
  你混淆了1-based索引的判断逻辑。假设k是1-based（比如第3小就是第三个最小的元素），正确的判断应该是：

  • 如果k-1 < len(smaller)：目标元素在smaller列表中（因为smaller里的所有元素都比pivot小，占了前len(smaller)个最小的位置）
  • 如果k-1 == len(smaller)：pivot就是第k小元素（smaller的元素加上pivot刚好是前k个最小的）
  • 否则目标在larger列表中
    原代码的len(smaller)<=k条件会把本该命中pivot的情况错误递归到smaller，完全颠倒了判断逻辑。

• 递归larger时未调整k值：
  当目标在larger列表时，前面已经有len(smaller)+1个比它小的元素（smaller的所有元素+当前pivot），所以需要将k减去这个数量，否则用原k值递归会找错位置。

• 缺少边界条件处理：
  当递归到空列表（比如k超出列表长度、递归路径错误）时，lst[0]会触发索引错误，需要先判断列表是否为空、k是否在有效范围内（1<=k<=len(lst)）。

修正后的代码 #

def findkth(lst, k):
    # 处理边界：空列表或k超出有效范围
    if not lst or k < 1 or k > len(lst):
        return None
    
    smaller = []
    larger = []
    pivot = lst[0]

    for num in lst[1:]:
        if num <= pivot:
            smaller.append(num)
        else:
            larger.append(num)
    
    # 1-based索引的逻辑判断
    if k - 1 < len(smaller):
        return findkth(smaller, k)
    elif k - 1 == len(smaller):
        return pivot
    else:
        # 调整k值，递归larger列表
        return findkth(larger, k - len(smaller) - 1)

mylst = [8,15,6,13,2,7,12,5,9,10]
print(findkth(mylst, 3))  # 输出5，正确的第3小元素

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