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.
max index(es) is the index for the first max value. If array is multidimensional, max index(es) is an array whose elements are the indexes for the first maximum value in array. min value is of the same data type and structure as the elements in array. min index(es) is the index for the first min value.
IndexOf(Array, Object, Int32) Searches for the specified object in a range of elements of a one-dimensional array, and returns the index of its first occurrence. The range extends from a specified index to the end of the 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 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 int
s 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:
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;
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With