Get indices of n maxima in java array

Question

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

The following is an example of the installation code and my attempt:

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 that the problem is that it constantly assigns the maximum maximum value to all the maximum elements. I am not sure how to fix this because I have to keep the values ​​and indexes of myArray .

I don't think sorting is an option because I need to keep indexes. In fact, these are the indices that I need specifically.

Answer 1

Sorting is an option due to additional 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 this is step 4 (n * lg n), like sorting. The whole algorithm is n lg n and is very simple to encode.

Here is a quick and dirty example. It may contain errors, and, obviously, zero checks, etc. Get into the game.

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 can choose a queue that simply tracks the largest 5. Being int , their values ​​should probably be boxed to be added to the collection (unless you flipped your own), which greatly increases overhead.

Answer 2

a little late in the answer, you can 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 3

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

Sort the copy if you want to keep the original order.

If you need indexes, there won't be a quick and dirty solution like in python or some other languages. You sort and browse, but it's ugly.

Or you can go objectively - it is, after all, java. Create an ArrayMaxFilter object. It will have a private class ArrayElement, which consists of an index and a value and has a natural ordering by value. It will have a method that takes a pair of ints, index and value, creates an ArrayElement from them and transfers them to a priority queue of length 5. (or whatever you look for). Send each pair of indexes / values ​​from the array, then report the values ​​left in the queue. (yes, the priority queue traditionally keeps the lowest values, but you can turn it around in your implementation)

Answer 4

My quick and small idea of ​​“think outside the box” was to use an EvictingQueue that contains a maximum of 5 elements. You had to pre-fill it with the first five elements from your array (do it in ascending order, so the first element you add is the lowest of the five).

Then you need to iterate over the array and add a new element to the queue when the current value is greater than the minimum value in the queue. To remember indexes, create a wrapper object (a pair of values ​​/ index).

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

This solution is O (n).

Answer 5

Here is my solution. Create a class that associates an index 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 the 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 an example of 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 

In the example I cited, only ten ints are generated with a value from 0 to 99 so that I can see that it worked. You can easily change this value to fit 1000 values ​​of any size. In addition, instead of starting 3 separate loops, I checked if the new value that I am adding is the maximum value immediately after adding to myArray . Give him a run and see if it works for you.