为什么这种快速选择算法并不总是有效

Question

我有一个简单的快速选择算法，想了解为什么它有时不起作用。 问题是找到

Top K Frequent Elements

。我知道还有其他方法可以做到这一点，例如使用堆或桶排序。但我很好奇为什么我的算法不起作用，因为我知道还有其他方法可以快速选择哪个工作。由于

random.choice

功能，它有时不起作用，这意味着可能会发生以下任何情况：

1. 得到正确的回应
2. 得到错误的回应
3. 面临最大递归深度超出错误

为什么？不是基于随机函数的快速选择，为什么其他使用 Python 函数实现随机性的快速选择算法可以工作，而这个却不行。我想念什么？

输入是数字列表

nums

和整数

k

 def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    histogram = Counter(nums) """ numbers frequency histogram/map"""
    def quickSelect(keys, k, ri = []):  
        r = random.choice(keys)  """ find the random key""" 
        pivot = histogram[r]  """ get the random frequency based on the random key"""
        left, right = [], [] """ put the keys in either right or left list based on their values"""
        for key in keys:
            if histogram[key] >= pivot:
                right.append(key)
            else:
                left.append(key) 
        if k == len(right) + len(ri): """ if the size of right plus previous right (ri) is equal to k we found it"""
            return right + ri
        elif k < len(right) + len(ri):
            return quickSelect(right, k, ri)         
        else:
            return quickSelect(left, k - len(right) - len(ri), right+ri)

    return quickSelect(list(histogram.keys()), k, [])

Answer 1

quickSelect(keys, k, ri = [])

递归时不会显式返回值 - 返回值为 None。

您不需要

ri

：操纵

k

。

防止像样的 quicksort 实现需要 O(n) 级递归的相同方法也适用于 quickSelect:
不要在较大的分区上递归。

但是检查一下你是否需要递归。