Python 递归辅助方法 returns none 而不是 int

Question

我想编写代码，以便我可以使用快速排序找到第 k 个最大的数字，并在 LeetCode 中编写了以下内容，LeetCode 将首先调用 findKthLargest

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 = i+1
               tmp = arr[counter] 
               arr[counter]=arr[i]
               arr[i]=tmp
            counter = counter+1
        temp = arr[i+1]
        arr[i+1]=arr[right]
        print('pivot '+str(piv)+' at '+str(i+1))
        arr[right]=temp
        print("at the nmoment "+str(arr))
        return (i+1)
    def helper(self,arr,left,right,k):
        if (left>=right):
            return 
        p = self.partition(arr,left,right)
        print("p is now "+str(p))
        if (p==len(arr)-k):
  
            return int(arr[p])
        self.helper(arr,left,p-1,k)
        self.helper(arr,p+1,right,k)
    def findKthLargest(self, nums, k):
        f= self.helper(nums,0,len(nums)-1,k)
        print(f)

我什至在辅助方法中打印了 (arr[p])，它给了我正确的答案，但是在方法 findKthLargest 中，变量 f 显示为 none 类型，我想知道我哪里做错了？目前我相信它正在返回一个 none 类型，因为在递归循环内部检查辅助方法中的 if (left>=right) 它 returns none

Answer 1

很难调试你的代码，这会用更少的语句通过：

class Solution:
    def findKthLargest(self, nums, k):
        def kth_smallest(nums, k):
            if nums:
                pos = partition(nums, 0, len(nums) - 1)
                if k > pos + 1:
                    return kth_smallest(nums[pos + 1:], k - pos - 1)
                elif k < pos + 1:
                    return kth_smallest(nums[:pos], k)
                else:
                    return nums[pos]

        def partition(nums, left, right):
            res = left
            while left < right:
                if nums[left] < nums[right]:
                    nums[left], nums[res] = nums[res], nums[left]
                    res += 1
                left += 1
            nums[res], nums[right] = nums[right],  nums[res]
            return res

        return kth_smallest(nums, len(nums) + 1 - k)

Answer 2

问题是您的 helper 函数并不总是 return 一个值。只有在 if 条件为真的基本情况下，它才会 return 一个数值。但它也应该 return 进行相应递归调用的相同数字。

所以改变：

self.helper(arr,left,p-1,k)
self.helper(arr,p+1,right,k)

至：

result = self.helper(arr,left,p-1,k)
if result is not None:
    return result
return self.helper(arr,p+1,right,k)

这样最深的 return 值将在递归树中冒泡，第一次递归调用成功将避免进行第二次递归调用。

Python 递归辅助方法 returns none 而不是 int

Python recursive helper method returns none instead of int

python

algorithm

recursion

quicksort