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

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

---

创建一个包含数字和索引的对象，然后创建这些对象的数组，然后执行Array.Sort（arrayset []，comparator）java docs。 然后，您可以从排序后的数组中挑选出前x个项目。

编辑：像这样的东西... [我用这个按照'距离'

import java.util.Arrays;
import java.util.Comparator;

public class NearestObject
{
    public NearestObject(int position, int distance)
    {
         this.Position = position;
         this.Distance = distance;
    }
    public int Position = 0;
    public int Distance = 0;

    public static NearestObject[] SortDistance(NearestObject[] items)
    {
        Arrays.sort(items, new DistanceSort());
        return items;
    }

}

class DistanceSort implements Comparator<NearestObject>
{
    public int compare(NearestObject o1, NearestObject o2)
    {
        return o1.Distance - o2.Distance;
    }
}

---

对数组进行排序然后选择10很简单，但它会是O（n log n），并且如果您不想重新排序初始数组，那么您也需要创建一个副本。

更好的办法是使用最大堆（或优先级队列），它在插入元素时自动对元素进行排序，这样最大的元素就是根节点。 沿着阵列走，继续投入元素，直到你达到10; 那么对于每个后续元素，只需检查它是否小于堆中最大的元素（恒定时间检查），如果是，则弹出该元素并插入新元素。 当你通过整个阵列时，剩下的10件事是你的最小元素。 这会让你在O（n log 10）== O（n）中得到你的结果，因为每次插入到堆中只会花费O（log 10）。

Java的Priority Queue实现默认为min-queue，因此您需要传入一个反转排序的Comparator。 看到这个问题的例子如何做到这一点。 如果你想在最后得到索引，你需要创建一个包含（值，索引）对的自定义对象。

---

直接的解决方案是遍历数组，并维护您找到的n个最小元素及其索引的列表。 这是一个O（N）解决方案，在大多数情况下都可以接受。 我猜尽管这是作业，你必须有比O（N）更好的东西。

链接地址: http://www.djcxy.com/p/37667.html

上一篇: get indexes of n smallest elements in an array

下一篇: How do I sort a list by different parameters at different timed