按顺序查找数组中最大的10%数字

Question

给定一个带有'N'个数字的数组(N> 100).我们怎样才能找到最大的10%？(如果n/10不是整数,我们可以将它舍入)

我提出了3种算法来尝试上述问题,但我不确定哪种算法在渐近运行时是最好的.我是否可以进行任何修改以减少渐近时间？此外,如果N变得非常大,哪种算法可能仍然有效？

我列出了我对以下算法的想法,并且可以真正使用一些帮助来找出最有效的算法.

ALGO-1

我使用选择排序并在10%的数字排序后停止它.

ALGO-2

我构建了一个最大堆并保持删除最大的10%的数字

ALGO-3

没有实现这个,但我的想法是使用任何order-statistic算法来查找包含前10%数字的分区,然后使用合并排序对它们进行排序.

Answer 1

最快的解决方案是使用基于分区的选择算法,该算法运行于O(n).它基于quicksort的想法,除了不是递归地对两个分区进行排序,你只需要去其中一个分区来找到k-th最小的元素.

找到最大的10%是通过搜索k=(90%*N)-th最小的数字来完成的.

如果您还记得quicksort中的分区是如何工作的,那么小于枢轴的元素将移动到左侧,其余元素将移动到右侧.假设您要选择k-th最小的元素.然后,您会看到k枢轴左侧是否至少有元素.如果有,那么您知道可以忽略右侧分区中的元素.否则,您可以忽略左侧分区中的所有元素,因为您知道该元素将位于正确的分区中.

请注意,选择算法仅识别那些前10%的数字.如果你需要对它们进行排序,那么你必须对这些数字进行排序(但只有那些数字,其他90%可以被忽略).

Answer 2

如果你知道 N，只需创建一个长度为其 1/10 的数组。每个单元格的初始值为 Int.MinValue。检查数组中的每个数字。如果它大于百分之十数组中的最小数字，则将其相加。

避免排序，但代价是不断扫描答案数组。您可以通过将其保持排序顺序来稍微抵消这一点，以便您可以使用二分搜索。