快捷導(dǎo)航

最大K個數(shù)問題的Python版解法總結(jié)

更新時間：2016年06月16日 18:09:39 作者：mattkang

這篇文章主要介紹了最大K個數(shù)問題的Python版解法總結(jié),以最大K個數(shù)問題為基礎(chǔ)的算法題目在面試和各大考試及競賽中經(jīng)常出現(xiàn),需要的朋友可以參考下

TopK問題,即尋找最大的K個數(shù),這個問題非常常見,比如從1千萬搜索記錄中找出最熱門的10個關(guān)鍵詞.
方法一:
先排序,然后截取前k個數(shù).
時間復(fù)雜度：O(n*logn)+O(k)=O(n*logn)。
這種方式比較簡單粗暴，提一下便是。

方法二：最大堆

我們可以創(chuàng)建一個大小為K的數(shù)據(jù)容器來存儲最小的K個數(shù)，然后遍歷整個數(shù)組，將每個數(shù)字和容器中的最大數(shù)進行比較，如果這個數(shù)大于容器中的最大值，則繼續(xù)遍歷，否則用這個數(shù)字替換掉容器中的最大值。這個方法的理解也十分簡單，至于容器的選擇，很多人第一反應(yīng)便是最大堆，但是python中最大堆如何實現(xiàn)呢？我們可以借助實現(xiàn)了最小堆的heapq庫，因為在一個數(shù)組中，每個數(shù)取反，則最大數(shù)變成了最小數(shù)，整個數(shù)字的順序發(fā)生了變化，所以可以給數(shù)組的每個數(shù)字取反，然后借助最小堆，最后返回結(jié)果的時候再取反就可以了，代碼如下：

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每趟只需要往一個方向走.
時間復(fù)雜度: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)

您可能感興趣的文章: