get indexes of n smallest elements in an array

I have an int array int[] myArray = new int[100]; and want to get indexes of smallest 10 (any n) elements. How can I do this?

---

make an object that contains the number and the index, then make an array of these objects, then perform Array.Sort(arrayset[], comparator) java docs. Then you can just pick out the top x items from the sorted array.

EDIT: Something like this... [I had used this to sort according to 'distance'

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;
    }
}

---

Sorting the array and then picking 10 is simple, but it'd be O(n log n), and if you don't want to re-order the initial array, you'd need to make a copy too.

A better idea is to use a max-heap (or priority queue), which automatically sorts elements as you insert them, such that the largest element is the root node. Walk along the array, keep putting in elements until you hit 10; then, for every subsequent element, simply check if it's smaller than the biggest element in the heap (constant-time check), and if it is, pop that one out and insert the new element. When you've passed through the entire array, the 10 things left inside are your minimum elements. This'll get you your result in O(n log 10) == O(n), since each insert into the heap will only cost O(log 10).

Java's Priority Queue implementation is a min-queue by default, so you'd need to pass in a Comparator that reverses the ordering. See this question for examples on how to do that. You'd need to create a custom object that contains (value, index) pairs too, if you want to get the indices out at the end.

---

The straight forward solution is to iterate over the array and maintain a list of the n smallest elements you've found and their indices. This is an O(N) solution, and acceptable in most cases. I'm guessing though that this is homework and you have to have something better than O(N).

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

上一篇: 弱引用的其他用途？

下一篇: 获取数组中n个最小元素的索引