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