获取数组中n个最小元素的索引

Question

我有一个int数组,int[] myArray = new int[100];并希望获得最小10(任意n)元素的索引.我怎样才能做到这一点？

Answer 1

对数组进行排序然后选择10很简单,但它是O(n log n),如果你不想重新排序初始数组,你也需要复制.

更好的想法是使用max-heap(或优先级队列),它会在插入元素时自动对元素进行排序,这样最大的元素就是根节点.沿着阵列走,继续放入元素,直到你达到10; 然后,对于每个后续元素,只需检查它是否小于堆中的最大元素(常量时间检查),如果是,则弹出那个并插入新元素.当你通过整个数组时,剩下的10件事是你的最小元素.这样就可以得到O(n log 10)== O(n)的结果,因为每次插入堆只需要花费O(log 10).

默认情况下,Java的Priority Queue实现是一个最小队列,因此您需要传入一个反转顺序的Comparator.有关如何执行此操作的示例,请参阅此问题.如果要在最后获取索引,则还需要创建包含(值,索引)对的自定义对象.