Python递归辅助方法返回None而非int：第k大元素快排实现问题排查

你的问题核心在于递归函数的返回值没有正确传递，导致findKthLargest最终拿到的是None。我们一步步拆解问题：

1. 递归返回值的丢失 #

当你的helper方法中找到目标位置p == len(arr)-k时，你确实返回了arr[p]，但这个返回值只传递给了上一层递归调用，而你并没有把这个值继续向上返回。同时，你调用左右子递归时，也没有接收它们的返回值并传递出去——这就导致即使下层递归找到了正确结果，上层也拿不到，最终整个helper方法默认返回None。

2. Base Case的缺失处理 #

当left >= right时，你直接return（没有返回值），但如果此时left == right的位置正好是我们要找的目标位置，这个分支也没有返回对应的值，直接返回了None。

3. 冗余的递归调用 #

快速排序找第k大元素不需要完全排序整个数组，我们只需要根据pivot的位置，递归目标所在的那一半即可，不需要同时递归左右两边——这不仅浪费性能，还会干扰返回值的传递。

修复后的代码 #

class Solution(object):
    def partition(self, arr, left, right):
        piv = arr[right]
        i = left - 1
        counter = left
        while counter < right:
            if arr[counter] < piv:
                i += 1
                arr[counter], arr[i] = arr[i], arr[counter]
            counter += 1
        arr[i+1], arr[right] = arr[right], arr[i+1]
        return i + 1

    def helper(self, arr, left, right, k):
        # Base Case：当区间只剩一个元素时，直接返回它
        if left == right:
            return arr[left]
        p = self.partition(arr, left, right)
        target_pos = len(arr) - k
        if p == target_pos:
            # 找到目标，直接返回
            return arr[p]
        elif p < target_pos:
            # 目标在右半区间，递归右半并返回结果
            return self.helper(arr, p+1, right, k)
        else:
            # 目标在左半区间，递归左半并返回结果
            return self.helper(arr, left, p-1, k)

    def findKthLargest(self, nums, k):
        return self.helper(nums, 0, len(nums)-1, k)

关键修改点说明 #

1. Base Case返回值：当left == right时，直接返回该位置的元素，确保即使递归到最后一个元素也能返回正确值。
2. 定向递归+返回传递：根据pivot位置和目标位置的关系，只递归需要的那一半区间，并且将递归调用的结果直接返回，确保结果能一直传递到最上层的findKthLargest。
3. 移除冗余递归：不再同时递归左右两边，避免无效计算和返回值干扰。

这样修改后，findKthLargest就能正确拿到helper返回的第k大元素了。

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