Get indices of n maximums in java array

Question

I have an array of size 1000. How can I find the indices (indexes) of the five maximum elements?

An example with setup code and my attempt are displayed below:

Random rand = new Random();
int[] myArray = new int[1000];
int[] maxIndices = new int[5];
int[] maxValues = new int[5];

for (int i = 0; i < myArray.length; i++) {
  myArray[i] = rand.nextInt();
}

for (int i = 0; i < 5; i++) {
  maxIndices[i] = i;
  maxValues[i] = myArray[i];
}

for (int i = 0; i < maxIndices.length; i++) {
  for (int j = 0; j < myArray.length; j++) {
    if (myArray[j] > maxValues[i]) {
      maxIndices[i] = j;
      maxValues[i] = myArray[j];
    }
  }
}

for (int i = 0; i < maxIndices.length; i++) {
  System.out.println("Index: " + maxIndices[i]);
}

I know the problem is that it is constantly assigning the highest maximum value to all the maximum elements. I am unsure how to remedy this because I have to preserve the values and the indices of myArray.

I don't think sorting is an option because I need to preserve the indices. In fact, it is the indices that I need specifically.

Answer 1

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

Answer 2

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 n
4. 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.

Answer 3

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

Answer 4

Easy O(nlogn) heap solution:

    public static List<Integer> getTopKIndices(List<Double> scores, int k) {
        Comparator<Map.Entry<Integer, Double>> comparator = Map.Entry.comparingByValue();
        PriorityQueue<Map.Entry<Integer, Double>> heap = new PriorityQueue<>(scores.size(), comparator.reversed());

        for (int i = 0; i < scores.size(); i++)
            heap.add(new AbstractMap.SimpleEntry<>(i, scores.get(i)));
        
        List<Integer> topKIndices = new LinkedList<>();
        for (int i = 0; i < k && !heap.isEmpty(); i++)
            topKIndices.add(heap.poll().getKey());

        return topKIndices;
    }

Answer 5

Arrays.sort(myArray), then take the final 5 elements.

Sort a copy if you want to preserve the original order.

If you want the indices, there isn't a quick-and-dirty solution as there would be in python or some other languages. You sort and scan, but that's ugly.

Or you could go objecty - this is java, after all. Make an ArrayMaxFilter object. It'll have a private class ArrayElement, which consists of an index and a value and has a natural ordering by value. It'll have a method which takes a pair of ints, index and value, creates an ArrayElement of them, and drops them into a priority queue of length 5. (or however many you want to find). Submit each index/value pair from the array, then report out the values remaining in the queue. (yes, a priority queue traditionally keeps the lowest values, but you can flip this in your implementation)

Answer 6

My quick and a bit "think outside the box" idea would be to use the EvictingQueue that holds an maximum of 5 elements. You'd had to pre-fill it with the first five elements from your array (do it in a ascending order, so the first element you add is the lowest from the five).

Than you have to iterate through the array and add a new element to the queue whenever the current value is greater than the lowest value in the queue. To remember the indexes, create a wrapper object (a value/index pair).

After iterating through the whole array, you have your five maximum value/index pairs in the queue (in descending order).

It's a O(n) solution.

Answer 7

Here is my solution. Create a class that pairs an indice with a value:

public class IndiceValuePair{
    private int indice;
    private int value;

    public IndiceValuePair(int ind, int val){
        indice = ind;
        value = val;
    }
    public int getIndice(){
        return indice;
    }
    public int getValue(){
        return value;
    }
}

and then use this class in your main method:

public static void main(String[] args){
    Random rand = new Random();
    int[] myArray = new int[10];
    IndiceValuePair[] pairs = new IndiceValuePair[5];
    System.out.println("Here are the indices and their values:");
    for(int i = 0; i < myArray.length; i++) {
        myArray[i] = rand.nextInt(100);
        System.out.println(i+ ": " + myArray[i]);
        for(int j = 0; j < pairs.length; j++){
            //for the first five entries
            if(pairs[j] == null){
                pairs[j] = new IndiceValuePair(i, myArray[i]);
                break;
            }
            else if(pairs[j].getValue() < myArray[i]){
                //inserts the new pair into its correct spot
                for(int k = 4; k > j; k--){
                    pairs[k] = pairs [k-1];
                }
                pairs[j] = new IndiceValuePair(i, myArray[i]);
                break;
            }
        }
    }
    System.out.println("\n5 Max indices and their values");
    for(int i = 0; i < pairs.length; i++){
        System.out.println(pairs[i].getIndice() + ": " + pairs[i].getValue());
    }
}

and example output from a run:

Here are the indices and their values:
0: 13
1: 71
2: 45
3: 38
4: 43
5: 9
6: 4
7: 5
8: 59
9: 60

5 Max indices and their values
1: 71
9: 60
8: 59
2: 45
4: 43

The example I provided only generates ten ints with a value between 0 and 99 just so that I could see that it worked. You can easily change this to fit 1000 values of any size. Also, rather than run 3 separate for loops, I checked to see if the newest value I add is a max value right after I add to to myArray. Give it a run and see if it works for you

Answer 8

I would suggest to use a PriorityQueue, which is a minmax head and has a complexity of O(n log k):

private int[] getTopKIndices(double[] array, int num) {
PriorityQueue<IndexValuePair> queue = new PriorityQueue<>(Comparator.comparingDouble((IndexValuePair value) -> value.value));

for (int i = 0; i < array.length; i++) {
    queue.offer(new IndexValuePair(i, array[i]));
    if (queue.size() > num) {
        queue.poll();
    }
}

int[] result = new int[num];
for (int i = 0; i < num; i++) {
    result[num - 1 - i] = queue.poll().index;
}

return result;

}

You could also use Google Guava for that (also n log k):

import com.google.common.collect.Ordering;    
private static int[] getTopKIndices(double[] array, int num) {
        List<IndexValuePair> pairs = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            pairs.add(new IndexValuePair(i, array[i]));
        }

        Comparator<IndexValuePair> valueComparator = Comparator.comparingDouble(value -> value.value);
        List<IndexValuePair> topKPairs = Ordering.from(valueComparator).greatestOf(pairs, num);

        int[] result = new int[num];
        for (int i = 0; i < num; i++) {
            result[i] = topKPairs.get(i).index;
        }

Simply comparing these implementaion in Java with Top 10 for 5 Mio entries gives you:

45411 ms for the solution with simple sorting
1815 ms for the priority queue
2086 ms for the guava solution