準備Java面試之排序基礎知識(二)

Java 編程語言 歐幾里得 教育 FairyWooBang 2017-04-19

題1

有20個數組,每個數組裡面有500個數,升序排列,求出這10000個數字中最大的500個,求複雜度。

題2

輾轉相處的時間複雜度是多少?

Tips1

解1:強算,合併數組,排序,求解;

解2:歸併排序,有點類似歸併的中間部分,20個數組逐個歸併,不斷拿到最大的500個,直到結束

但是還有一個解3.

Tips2

輾轉相除法,又稱歐幾里得算法,用於求兩個自然數的最大公約數。

解1

利用堆。保持一個20的堆,然後先將每個數組的第1個數入堆。20個元素的堆一直保持容量為20個,20個數組的最小元素可以將20個數組的第0個元素入堆,最小堆的性質,頂點為最小值。這時候得到了500個結果裡的第0個結果。然後再把下一個元素入20個元素的堆,堆插入的時候會保持性質不變,最小元素依然在頂點。再取出20個元素的頂點,得到500個結果裡的第1個結果。

解2

算法的數論等式gcd(a,b) = gcd(b, a mod b),其時間複雜度為O(logn)。

相關推薦

推薦中...