在java数组中获取n个最大值的索引

Question

我有一个大小为1000的数组。我如何找到五个最大元素的索引（索引）？

与设置代码和我尝试的例子显示如下：

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

我知道的问题是，它是不断赋予最高的最大值，所有最大的元素。我不确定如何解决这个问题，因为我必须保留myArray的值和索引。

我不认为排序是一种选择，因为我需要保留指数。实际上，这是我特别需要的指标。

Answer 1

排序是一个选项，以增加内存为代价。考虑以下算法。

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) 

因此，第4步是（n * lg n），就像排序。整个算法是n lg n，编码非常简单。

这是一个快速而肮脏的例子。其中可能存在一些错误，并且显然无效检查等会发挥作用。

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

} 

还有其他的事情可以做，以减少此操作的开销。例如，您可以选择使用一个队列来跟踪最大的队列，而不是排序，因为它们的值可能必须加框才能添加到集合中（除非您自己推出），这会显着增加开销。

Answer 2

Arrays.sort（myArray），然后取最后的5个元素。

如果要保留原始顺序，请对副本进行排序。

如果你想要的索引，没有一个快速和肮脏的解决方案，因为会在Python或其他语言。你排序和扫描，但这是丑陋的。

或者你可以去对象 - 毕竟这是java。 制作一个ArrayMaxFilter对象。它将拥有一个私有类ArrayElement，它由一个索引和一个值组成，并且按值自然排序。它会有一个方法，它需要一对ints，索引和值，创建一个ArrayElement，并将它们放入一个长度为5的优先级队列（或者你想找的很多）。提交数组中的每个索引/值对，然后报告队列中剩余的值。 （是的，一个优先级队列传统上保持最低值，但你可以在你的实现中翻转这个）

Answer 3

我的快速和有点“想到外面”的想法是使用EvictingQueue，最多保留5元素。你必须预先填充数组中的前五个元素（按照升序排列，所以你添加的第一个元素是五个中最低的元素）。

只要当前值大于队列中的最小值，就必须遍历数组并向队列中添加一个新元素。要记住索引，请创建一个包装对象（值/索引对）。

遍历整个数组后，队列中有五个最大值/索引对（按降序排列）。

这是一个O（n）解决方案。

Answer 4

这是我的解决方案。创建一个类，对具有价值的指数之：

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

，然后在你的主要方法，使用这个类：

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 

的：从运行

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

和示例输出举例来说，我只提供了10个整数，其值在0到99之间，这样我就可以看到它的工作。您可以轻松地将其更改为适合任何尺寸的1000个值。此外，我并没有运行3个单独的for循环，而是在添加到myArray之后，检查我添加的最新值是否为最大值。给它一个运行，看看它是否在回答对你的作品

Answer 5

有点晚了，你也可以使用这个功能，我写道：

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