最大K個數問題的Python版解法

TopK問題,即尋找最大的K個數,這個問題非常常見,比如從1千萬搜尋記錄中找出最熱門的10個關鍵字.

方法一:
先排序,然後截取前k個數.
時間複雜度：O(n*logn)+O(k)=O(n*logn)。
這種方式比較簡單粗暴，提一下便是。

方法二：最大堆

我們可以建立一個大小為K的資料容器來儲存最小的K個數，然後遍歷整個數組，將每個數字和容器中的最大數進行比較，如果這個數大於容器中的最大值，則繼續遍歷，否則用這個數字替換掉容器中的最大值。這個方法的理解也十分簡單，至於容器的選擇，很多人第一反應便是最大堆，但是python中最大堆如何實現呢？我們可以藉助實現了最小堆的heapq庫，因為在一個數組中，每個數取反，則最大數變成了最小數，整個數字的順序發生了變化，所以可以給數組的每個數字取反，然後借助最小堆，最後回傳結果的時候再取反就可以了，程式碼如下：

#

import heapq
def get_least_numbers_big_data(self, alist, k):
  max_heap = []
  length = len(alist)
  if not alist or k <= 0 or k > length:
    return
  k = k - 1
  for ele in alist:
    ele = -ele
    if len(max_heap) <= k:
      heapq.heappush(max_heap, ele)
    else:
      heapq.heappushpop(max_heap, ele)

  return map(lambda x:-x, max_heap)


if __name__ == "__main__":
  l = [1, 9, 2, 4, 7, 6, 3]
  min_k = get_least_numbers_big_data(l, 3)

方法三：quick select

quick select演算法.其實就類似快排.不同地方在於quick select每趟只需要往一個方向走.
時間複雜度:O(n).

def qselect(A,k): 
  if len(A)<k:return A 
  pivot = A[-1] 
  right = [pivot] + [x for x in A[:-1] if x>=pivot] 
  rlen = len(right) 
  if rlen==k: 
    return right 
  if rlen>k: 
    return qselect(right, k) 
  else: 
    left = [x for x in A[:-1] if x<pivot] 
    return qselect(left, k-rlen) + right 
 
for i in range(1, 10): 
  print qselect([11,8,4,1,5,2,7,9], i)

更多最大K個數問題的Python版解法相關文章請關注PHP中文網！

#