一道java面試題，20億數(shù)字的文本排序，如何取前100？因?yàn)檫@是一個(gè)Java問(wèn)題，所以這是典型的TOPK問(wèn)題。首先取前100個(gè)數(shù)字構(gòu)建一個(gè)最小堆，然后依次從堆的頂部插入剩余的數(shù)字，同時(shí)調(diào)整堆。堆中最

一道java面試題，20億數(shù)字的文本排序，如何取前100？

因?yàn)檫@是一個(gè)Java問(wèn)題，所以這是典型的TOPK問(wèn)題。首先取前100個(gè)數(shù)字構(gòu)建一個(gè)最小堆，然后依次從堆的頂部插入剩余的數(shù)字，同時(shí)調(diào)整堆。堆中最后100個(gè)元素就是結(jié)果?？臻g復(fù)雜度是k，時(shí)間復(fù)雜度是nlogk

對(duì)于這個(gè)問(wèn)題，我考慮了一段時(shí)間，想出了一個(gè)比較愚蠢的方法。如果你有其他方法，請(qǐng)給我你的建議。

讓我們明確一下，我們需要購(gòu)買(mǎi)所有四種雞?；蛘邆鹘y(tǒng)的思維方式，建立未知，建立方程。你看，有四個(gè)未知數(shù)，兩個(gè)方程式。為了順利地解決這個(gè)問(wèn)題，我們可以假設(shè)C和D是已知量，這樣a和B可以用含有C和D的公式來(lái)表示，請(qǐng)注意這里的C只能取3的整數(shù)倍，如3、6、9等，這里的D只能取4的整數(shù)倍，如4、8、12等，公式中有一個(gè)分?jǐn)?shù)，不易計(jì)算，容易出錯(cuò)，需要更換。當(dāng)m等于1時(shí)，n的值由a和B的表達(dá)式確定。其他解也可以用同樣的方法得到。