-3

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?

9
  • It would help the community to better help if you showed what you have attempted. Specifically, if you are trying some code and it is not working well, it would be best to show us the snippet that seems to not be working correctly for you.
    – aperkins
    May 6, 2010 at 20:44
  • @erasmus He is asking if this is for homework or not. Question tagged as homework receive different answers. For instance How do I sort an array with [homework] tag will lead to an explanation of different sorting algorithms, with out it, will get Arrays.sort( list );
    – OscarRyz
    May 6, 2010 at 20:47
  • @Oscar, I don't think he is sincere. There are some people like him. what they do is decreasing questions's vote values and writing some provocative comments. that guys are just useless things.
    – erasmus
    May 6, 2010 at 20:54
  • @erasmus: Sometimes the question are posted in an unclear way. I had to read it several times until because I didn't quite get it. I added my answer, see if it's what you need.
    – OscarRyz
    May 6, 2010 at 21:21
  • @erasmus: I have to agree with Oscar here - the question looked to me to be a homework style question.
    – aperkins
    May 6, 2010 at 21:30

6 Answers 6

11

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.

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

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

5
  • 1
    Isn't it O(n*m)? (n=input size, m=number items)
    – Kurru
    Mar 1, 2011 at 20:14
  • @Kurru, Admittedly the specifics of my answer aren't entirely clear. I think this question was tagged homework before. I don't think it is O(NM) because one does not have to iterate over the list of M elements. Once the Mth smallest element is found, all subsequent iterations over the list of N merely need to check themselves against the Mth element. I suppose that behavior is best facilitated by using a priority heap. So... O(Nlog(M)) ???
    – Tim Bender
    Mar 1, 2011 at 21:48
  • So I guess my answer was just a less descriptive version of @tzaman's answer.
    – Tim Bender
    Mar 1, 2011 at 21:53
  • Does a priority loop have log(M) insert and read in the worst case? Didn't know that
    – Kurru
    Mar 2, 2011 at 0:27
  • When reading a heap one is usually concerned with the min or max value, implementations usually allow a read complexity of O(1). Insert/delete complexity of O(logN). Here is Java's PriorityQueue: download.oracle.com/javase/6/docs/api/java/util/… The last line of the javadoc for the class describes the time complexities guaranteed by the current implementation.
    – Tim Bender
    Mar 2, 2011 at 2:23
2

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

    }
}
0

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.

0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.