在数组中找到最低最高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