快捷導(dǎo)航

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

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

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

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

方法二：最大堆

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

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算法.其實(shí)就類似于快排.不同地方在于quick select每趟只需要往一個(gè)方向走.
時(shí)間復(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)

您可能感興趣的文章: