TopK問題,即尋找最大的K個數,這個問題非常常見,比如從1千萬搜索記錄中找出最熱門的10個關鍵詞.
方法一:
先排序,然后截取前k個數.
時間復雜度：O(n*logn)+O(k)=O(n*logn)。
這種方式比較簡單粗暴，提一下便是。
方法二：最大堆
我們可以創建一個大小為K的數據容器來存儲最小的K個數，然后遍歷整個數組，將每個數字和容器中的最大數進行比較，如果這個數大于容器中的最大值，則繼續遍歷，否則用這個數字替換掉容器中的最大值。這個方法的理解也十分簡單，至于容器的選擇，很多人第一反應便是最大堆，但是python中最大堆如何實現呢？我們可以借助實現了最小堆的heapq庫，因為在一個數組中，每個數取反，則最大數變成了最小數，整個數字的順序發生了變化，所以可以給數組的每個數字取反，然后借助最小堆，最后返回結果的時候再取反就可以了，代碼如下：
import heapqdef 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)
新聞熱點
疑難解答
圖片精選
