Get indices of n maximums in java array

Sorting is an option, at the expense of extra memory. Consider the following algorithm.

1. Allocate additional array and copy into - O(n)2. Sort additional array - O(n lg n)3. Lop off the top k elements (in this case 5) - O(n), since k could be up to n4. Iterate over the original array - O(n)    4.a search the top k elements for to see if they contain the current element - O(lg n)

So it step 4 is (n * lg n), just like the sort. The entire algorithm is n lg n, and is very simple to code.

Here's a quick and dirty example. There may be bugs in it, and obviously null checking and the like come into play.

import java.util.Arrays;

class ArrayTest {    public static void main(String[] args) {        int[] arr = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};        int[] indexes = indexesOfTopElements(arr,3);        for(int i = 0; i < indexes.length; i++) {            int index = indexes[i];            System.out.println(index + " " + arr[index]);        }    }    static int[] indexesOfTopElements(int[] orig, int nummax) {        int[] copy = Arrays.copyOf(orig,orig.length);        Arrays.sort(copy);        int[] honey = Arrays.copyOfRange(copy,copy.length - nummax, copy.length);        int[] result = new int[nummax];        int resultPos = 0;        for(int i = 0; i < orig.length; i++) {            int onTrial = orig[i];            int index = Arrays.binarySearch(honey,onTrial);            if(index < 0) continue;            result[resultPos++] = i;        }        return result;    }}

There are other things you can do to reduce the overhead of this operation. For example instead of sorting, you could opt to use a queue that just tracks the largest 5. Being ints they values would probably have to be boxed to be added to a collection (unless you rolled your own) which adds to overhead significantly.

Sorry to answer this old question but I am missing an implementation which has all following properties:

• Easy to read
• Performant
• Handling of multiple same values

Therefore I implemented it:

    private int[] getBestKIndices(float[] array, int num) {        //create sort able array with index and value pair        IndexValuePair[] pairs = new IndexValuePair[array.length];        for (int i = 0; i < array.length; i++) {            pairs[i] = new IndexValuePair(i, array[i]);        }        //sort        Arrays.sort(pairs, new Comparator<IndexValuePair>() {            public int compare(IndexValuePair o1, IndexValuePair o2) {                return Float.compare(o2.value, o1.value);            }        });        //extract the indices        int[] result = new int[num];        for (int i = 0; i < num; i++) {            result[i] = pairs[i].index;        }        return result;    }    private class IndexValuePair {        private int index;        private float value;        public IndexValuePair(int index, float value) {            this.index = index;            this.value = value;        }    }

a bit late in answering, you could also use this function that I wrote:

/**  * Return the indexes correspond to the top-k largest in an array.  */public static int[] maxKIndex(double[] array, int top_k) {    double[] max = new double[top_k];    int[] maxIndex = new int[top_k];    Arrays.fill(max, Double.NEGATIVE_INFINITY);    Arrays.fill(maxIndex, -1);    top: for(int i = 0; i < array.length; i++) {        for(int j = 0; j < top_k; j++) {            if(array[i] > max[j]) {                for(int x = top_k - 1; x > j; x--) {                    maxIndex[x] = maxIndex[x-1]; max[x] = max[x-1];                }                maxIndex[j] = i; max[j] = array[i];                continue top;            }        }    }    return maxIndex;}