最大K個(gè)數(shù)問(wèn)題的Python版解法總結(jié)
TopK問(wèn)題,即尋找最大的K個(gè)數(shù),這個(gè)問(wèn)題非常常見,比如從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)
相關(guān)文章
今天小編就為大家分享一篇對(duì)TensorFlow的assign賦值用法詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-07-07
這篇文章主要介紹了詳解用python的階乘，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-10-10
python實(shí)現(xiàn)字符串字母大小寫轉(zhuǎn)換的幾種方法
本文主要介紹了python實(shí)現(xiàn)字符串字母大小寫轉(zhuǎn)換的幾種方法,包括islower()、isupper()、istitle()、lower()、casefold()、upper()、capitalize()、title()和swapcase(),具有一定的參考價(jià)值,感興趣的可以了解一下2025-03-03
分析用Python腳本關(guān)閉文件操作的機(jī)制
這篇文章主要介紹了分析用Python腳本關(guān)閉文件操作的機(jī)制,作者分Python2.x版本和3.x版本兩種情況進(jìn)行了闡述,需要的朋友可以參考下2015-06-06
Python采集二手車數(shù)據(jù)的超詳細(xì)講解
這篇文章主要為大家介紹了Python采集二手車數(shù)據(jù)實(shí)現(xiàn)的超詳細(xì)講解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-04-04
Pyqt5 實(shí)現(xiàn)跳轉(zhuǎn)界面并關(guān)閉當(dāng)前界面的方法
今天小編就為大家分享一篇Pyqt5 實(shí)現(xiàn)跳轉(zhuǎn)界面并關(guān)閉當(dāng)前界面的方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-06-06
使用python 將圖片復(fù)制到系統(tǒng)剪貼中
今天小編就為大家分享一篇使用python 將圖片復(fù)制到系統(tǒng)剪貼中，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-12-12
解決python 出現(xiàn)unknown encoding: idna 的問(wèn)題
這篇文章主要介紹了解決python出現(xiàn) unknown encoding: idna 的問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2021-03-03
深入了解Python中Pytest Markers的使用方法
從這篇開始,逐一解決fixture是啥,mark是啥,參數(shù)request是啥,鉤子函數(shù)是啥,parametrize參數(shù)化是啥,這些問(wèn)題,本片先介紹一下mark是啥,以及如何使用2023-09-09
python編程冒泡排序法實(shí)現(xiàn)動(dòng)圖排序示例解析
這篇文章主要介紹了python編程中如何使用冒泡排序法實(shí)現(xiàn)動(dòng)圖排序的示例解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步2021-10-10