我有一个简单的快速选择算法，并想了解为什么它不工作 * 有时 *。问题是找到Top K Frequent Elements。我知道还有其他方法可以做到这一点，如使用堆或桶排序。但我很好奇为什么我的算法不工作，因为我知道有其他方法来做快速选择工作。由于random.choice函数，它有时无法工作，这意味着可能发生以下任何情况：
1.得到正确的回答
1.得到不正确的响应
1.面最大递归深度超出错误
为什么？快速选择不是基于随机函数的吗？为什么其他使用Python函数进行随机的快速选择算法可以工作，而这个却不行。我错过了什么
输入是一个数字列表，如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, [])

字符串

更新

它根据所接受的响应建议工作。添加了其他解决方法作为评论以及那些谁感兴趣。

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

    ####heap in O(nlogk)
    # histogram = Counter(nums)
    # return heapq.nlargest(k, histogram.keys(), key = histogram.get)

    ####bucket sort in 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

       #### quick select 
       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)

型