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中文網！
#
