勵(lì)志當(dāng)最強(qiáng)課代表的我來給大家總結(jié)總結(jié)??????

大廠面試題】如何在一億個(gè)數(shù)中找出最大的1萬個(gè)數(shù)？

總結(jié):

一、軟件應(yīng)用的問題??

二、軟件應(yīng)用的看法??

三、軟件應(yīng)用的結(jié)論??

一、軟件應(yīng)用的問題???

?大廠面試題】如何在一億個(gè)數(shù)中找出最大的1萬個(gè)數(shù)？

二、軟件應(yīng)用的看法??

?1.快速排序法

最先想到的大概就是使用快速排序算法，遍歷所有數(shù)據(jù),進(jìn)行排序后，取出最前面的10000個(gè)，時(shí)間復(fù)雜度為0 (nlogn)，1個(gè)數(shù)字按照4字節(jié)來算，最多占用40口MB。一般來說我們的機(jī)器內(nèi)存是可以撐住的，但是這種主要是效率不高，我們只要前1 000 0個(gè)，在排序的過程中,我們會(huì)浪費(fèi)很多時(shí)間去做無用功。

?2.淘汰法

先用一個(gè)list保存前10000個(gè)數(shù)字，然后遍歷剩下的數(shù)字，如果某一個(gè)數(shù)字比容器中的數(shù)字大，那么刪除掉容器中的數(shù)據(jù)進(jìn)行替換，假如說后面的數(shù)字正好都比前面的小，那么容器中的就是最大的。時(shí)間復(fù)雜度為0 (n+m^2 )

?3.分治法

將1億個(gè)數(shù)據(jù)分成10000份，每份10000萬個(gè)數(shù)據(jù)，用多線程然后使用快速排序來找到每份數(shù)據(jù)中最大的10000個(gè)，最后在剩下的數(shù)據(jù)里面快速排序找出最大的10000個(gè)。這樣我們的效率會(huì)很高，提升了CPU的利用率。相比第一種方法，我們提高了100倍的速度。

?4.最小堆算法

首先讀入前10000個(gè)數(shù)來創(chuàng)建大小為10000的最小堆，建堆的時(shí)間復(fù)雜度為0(mlogm)(m為數(shù)組的大小即為1口000)，然后遍歷后續(xù)的數(shù)字，并于堆頂( 最小)數(shù)字進(jìn)行比較。如果比最小的數(shù)小，則繼續(xù)讀取后續(xù)數(shù)字;如果比堆頂數(shù)字大，則替換堆頂元素并重新調(diào)整堆為最小堆。整個(gè)過程直至1億個(gè)數(shù)全部遍歷完為止。然后按照中序遍歷的方式輸出當(dāng)前堆中的所有10000個(gè)數(shù)字。該算法的時(shí)間復(fù)雜度為0 (nmlogm)，空間復(fù)雜度是I oooo(常數(shù))

三、軟件應(yīng)用的結(jié)論??

?學(xué)習(xí)以上內(nèi)容