get indexes of n smallest elements in an array

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

Sort them by index and return the first 10

First create the structure to hold both, index and value:

class IndexValue {
   final int i;
   final int v;
}

Then create an array with this new structure:

IndexValue[] array = new IndexValue[myArray.length];
for( int i = 0 ; i < array.length ; i++ ) {
    array[i] = new IndexValue( i, myArray[i] );
}

Finally sort it and take the first N elements

Arrays.sort( array ); // you'll need to implement Comparator though 

for( int i = 0 ; i< 10 ;i++ ) {
    System.out.print( array[i] );
}

Here's the full working code:

import java.util.Arrays;
import java.util.Random;
import java.util.Comparator;
import static java.lang.System.out;

class IndexValue {
   final int i,v;

   public IndexValue( int i, int v ) {
       this.i = i;
       this.v = v;
   }
}
public class SortByIndex {
    public static void main( String [] args ) {

        Random random = new Random();

        int [] myArray = new int[100];
        IndexValue[] array = new IndexValue[myArray.length];

        // Fill the array 
        for( int i = 0 ; i < 100; i++ ) {
            myArray[i] = random.nextInt();
            array[i] = new IndexValue( i, myArray[i] );
        }

        // Sort it 
        Arrays.sort( array, new Comparator<IndexValue>(){
            public int compare( IndexValue a, IndexValue b ){
                return a.v - b.v;
            }
        });

        // Print it
        out.println("Top:");
        for( int i = 0 ; i < 10 ; i++ ) {
            out.println( String.format("array[%d]=%d",  array[i].i, array[i].v ));
        }

    }
}

Answer 4

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).

Answer 5

You can sort the array, loop the first 10 elements and then for each element search into the array which position it has... maybe it's not the more efficient way, but it's the easier one.

Answer 6

If you are looking for a practical answer (versus the actual sorting alg., etc.), then just use a HashMap or PriorityQueue. If speed isn't a concern try this easy alg. It is easier than a PriorityQueue since you don't need a custom object:

HashMap<Integer, ArrayList<Integer>> indexMap = new HashMap<Integer, ArrayList<Integer>>();

Fill indexMap so we can get the indices for any given number in array

for (int index = 0; index <= array.size; index++) {
   if (indexMap.get(array[index]) == null) { // Prime it with an ArrayList
      indexMap.put(array[index], new ArrayList<Integer>());
   }

   indexMap.get(array[index]).add(index);
}

For the smallest n numbers in array, print out their index.

Arrays.sort(array);
for (int index = 0; index <= n; index++) {
   System.out.println(indexMap.get(array[index]).remove(0));
}