在數組中找到最低最高10％的僞代碼

Question

我需要在數組中找到最低和最高10％的數字，交易是我需要它非常快速地工作！

例如，對於數組：20,50,77,80,6,8,41,60,63,15,31,13,90,9,34,41,54,85​​,93,2， 52

我最初的解決辦法是用快速排序對數組進行排序：

2,6,8,9,13,15,20,31,34,41,50,52,54,60， 63,77,80,85,90,93

然後我很容易知道自己的最高和最低的10％

低：2,6 高：90,93

但問題是這個數組變化非常快，排序解決方案對我無效。任何人都有建議如何快速找到我需要的東西？

Answer 1

我沒有看到比排序另一種解決方案。但是，如果你在你自己的數據結構組織的事情的自由和控制輸入數組，你可以這樣做，也許這可以節省時間：

1. 創建一個有序列表（或其他有序結構）的大小10％的原始數組。提供方法將元素添加到此有序列表中。另一個答案提出了B樹，這也可能用於這種方法。
2. 將元素添加到原始數組時，還將該元素添加到您的有序列表中
3. 有序列表將始終包含前10％。

對於大數據集，Aston方法的改進可能非常小，因爲該算法只會增加我的對數尺度。然而，如果您的數據集很小，那麼僅使用10％大小的有序數據結構可能會帶來真正的好處。

注：如果元素從原始數組中刪除，我的做法可能會比只使用阿斯頓建議從一開始不太好，因爲去除的元素可能會觸發一個完整的運行在列表再次完全填充有序結構。

Answer 2

我認爲你需要考慮使用不同的數據結構來存儲你的數據。例如，使用B樹意味着您可以插入和刪除對數時間的元素，但您的數據仍然被排序，因此您可以在普通數組中同時獲得最低和最高10％。

http://en.wikipedia.org/wiki/B-tree