为何我的快速选择算法无法稳定运行？——Top K高频元素问题排查

我实现了一个求解Top K高频元素的快速选择算法，但无法稳定运行：有时返回正确结果，有时结果错误，还会触发「maximum recursion depth exceeded」错误。我知道可以用堆排序、桶排序等方法解决该问题，也了解存在可正常运行的快速选择实现，但疑惑为何同样使用random.choice的我的算法会出现问题，希望排查原因。输入为数字列表nums和整数k，原实现代码如下：

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    histogram = Counter(nums) """ nums' 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):
            quickSelect(right, k, ri)         
        else:
            quickSelect(left, k - len(right) - len(ri), right+ri)

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

原代码的核心问题 #

1. 递归调用未返回结果：在elif和else分支中，调用quickSelect后没有通过return传递结果。这会导致递归深层的正确结果无法向上传递，最终外层函数返回None，出现结果错误。
2. 可变默认参数陷阱：函数参数ri = []使用了可变对象作为默认值。Python中默认参数仅在函数定义时初始化一次，后续调用若未显式传入ri，会复用同一个列表，导致历史数据累积，破坏逻辑正确性。
3. 分区逻辑导致的递归深度问题：将所有频率大于等于基准的元素都放入right列表，当存在大量频率相同的元素时，每次递归的问题规模无法有效缩小，极端情况会退化为O(n²)时间复杂度，触发递归深度溢出。

修正后的实现及其他参考方案 #

根据可行方案修正后算法可正常运行，同时附上堆排序、桶排序的实现供参考：

def topKFrequent(self, nums: List[int], k: int) -> List[int]:

####堆排序 O(nlogk)
# histogram = Counter(nums)
# return heapq.nlargest(k, histogram.keys(), key = histogram.get)

####桶排序 O(n)
# bucket = [[] for _ in range(len(nums)+1)]
# histogram = Counter(nums)
# for n, f in histogram.items():
#     bucket[f].append(n)
# res = []
# for i in range(len(bucket)-1, -1, -1):
#     if bucket[i]:
#         for n in bucket[i]:
#             res.append(n)
#             if len(res) == k:
#                 return res          
# return None

   #### 快速选择 
   histogram = Counter(nums) 
   def quickSelect(keys, k):  
      pivot = histogram[random.choice(keys)]
      left, right = [], []
      for key in keys:
          if histogram[key] >= pivot:
              right.append(key)
          else:
              left.append(key) 
      if k == len(right):
          return right
      elif k < len(right):
          return quickSelect(right, k)         
      else:
          return quickSelect(left, k - len(right)) + right
   return quickSelect(list(histogram.keys()), k)

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