【問(wèn)題描述】

有很多無(wú)序的數(shù)，我們姑且假定它們各不相等，怎么選出其中最大的若干個(gè)數(shù)呢？

方法一：時(shí)間復(fù)雜度min(O(nlogn), O(nk))

idea 1:

先用快速排序或者堆排序進(jìn)行排序，然后取出最大的k個(gè)數(shù)，時(shí)間復(fù)雜度為O(nlogn)+O(k)=O(nlogn)

idea 2:

進(jìn)行k趟最大冒泡或者k次大頂堆的輸出，時(shí)間復(fù)雜度為O(n*k)

根據(jù)k與logn的大小比較，選取時(shí)間復(fù)雜度低的算法

方法二：時(shí)間復(fù)雜度O(nlogk)

方法三：時(shí)間復(fù)雜度為O(n*log( |Vmax - Vmin|? / delta))，數(shù)據(jù)分布均勻時(shí)，時(shí)間復(fù)雜度為O(nlogn)

尋找N個(gè)數(shù)中最大的k個(gè)數(shù)，重點(diǎn)在于宣召最大的k個(gè)數(shù)中最小的那個(gè)，也就是第k大的數(shù)。

方法四：用小頂堆

用容量為k的小頂堆來(lái)存儲(chǔ)最大k個(gè)數(shù)，從數(shù)列中取一個(gè)數(shù)X與當(dāng)前的堆頂元素Y比較，若X>Y，則交換，然后調(diào)整堆，否則取下一個(gè)數(shù)進(jìn)行判斷，以此判斷直到所有的數(shù)都判斷完畢。調(diào)整堆的時(shí)間復(fù)雜度為O(logk)

調(diào)整更新的偽代碼為：

方法五：

所有整數(shù)都在(0, max)區(qū)間的話，用數(shù)組count[max]存儲(chǔ)每個(gè)數(shù)的出現(xiàn)次數(shù)。只需掃描一遍即可得到count數(shù)組，然后尋找最大的k個(gè)數(shù)。

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的编程之美-寻找最大的k个数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。