計算澳第90百分位數（n）的時間

可能重複：
Can you sort n integers in O(n) amortized complexity?計算澳第90百分位數（n）的時間

我必須寫一個給定的整數未排序的算法，則返回「最低文件中的數字至少超過文件中90％的數字「，如果不存在這樣的數字，則爲-1。足夠簡單：我使用合併排序對列表進行排序，然後從90％的索引處開始，並查找第一個數字，使其大於之前的數字。

問題的第2部分已經得到了我雖然難住了。我們得到更多的信息：整數代表薪水，意味着他們都是積極的，其中絕大多數都低於100萬。顯然，有了這些額外的信息，就有可能編寫一個算法來解決O（n）時間中的原始問題，但我沒有絲毫的線索知道這是可能的。有任何想法嗎？

我會寄我到目前爲止已經做了，但我一直沒能拿出任何東西。

來源

2012-11-12 GMA

所有元素有一個選擇算法可以用於此。擡頭看看Cormen。還有用於排序的線性時間算法。 –

你正在尋找一個selection algorithm，其選擇在陣列的第k最大元素。維基百科的文章給出了一個O（n）算法來做到這一點，它類似於快速排序，但不排序整個數組，因此避免了O（n * logn）運行時間。

如果元素都在一定的範圍內（例如1-1000000），那麼另一種方法是在O（n）中使用counting sort或bucket sort進行排序，然後選擇您需要的元素。因爲在這種情況下，元素的「絕大多數」 1000000，而不是所有的人都在，你可以用水桶1000001執行桶排序，並使用最後一個桶上面1000000

來源

2012-11-12 15:49:07 interjay

對於不想閱讀維基百科文章誰的人：在O（n）的基於比較的選擇算法就像是快速排序，除了分割後陣，你就包含您要選擇的指數的一側只有復發。 –

「您可以使用1000001個存儲分區執行存儲分區排序，併爲1000000以上的所有元素使用最後一個存儲分區。」工程魅力。謝謝！ – GMA

計算澳第90百分位數（n）的時間

回答

相關問題