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

Question

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

以下是设置代码和我的尝试示例：

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的值和索引。 我认为排序不是一个选项，因为我需要保留索引，实际上，我特别需要的就是索引。

- Brian

---

看起来你需要重新考虑如何在发现前五个新元素时进行更新。 - Louis Wasserman

在这个讨论中有一些保持索引的方法。 - Michael Lang

你已经非常接近正确的方法了，你只需要重新调整第三个循环即可。 - Louis Wasserman

你能使用ArrayList吗？这可能会导致更简单的算法。 - mistahenry

首先获取第一个最大值的索引。 - Code-Apprentice

Answer 1

很抱歉回答这个老问题，但我缺少一个具有以下所有属性的实现：

• 易于阅读
• 高性能
• 处理多个相同值

因此，我进行了实现：

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

- Klaus

Answer 2

排序是一种选项，但需要额外的内存。考虑以下算法。

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)

所以第四步是(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;
    }

}

有其他方法可以减少此操作的开销。例如，您可以选择使用一个仅跟踪最大5个元素的队列，而不是进行排序。由于这些值是int类型，因此它们可能需要被装箱以添加到集合中（除非您自己编写了代码），这会显著增加开销。

- corsiKa

---

@TheNewIdiot - 正确的用法是 lg 而不是 log。而且 4.a 不同于 5，因为它不是一个不同的步骤 - 它是在迭代过程中发生的事情。 - corsiKa

@Hunter 有点类似。lg 表示以 2 为底的对数。在大 O 表示法中，它们会被压缩到同一阶级，这是正确的。但是，如果这种更改已经被审查过，那么它将被拒绝，因为它被认为是“太小”的更改，而将 4.a 更改为 5 将被拒绝，因为它是“不正确的”。 - corsiKa

Answer 3

有点晚了，但你也可以使用我编写的这个函数：

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

- user3879337

---

尝试使用一些条件来避免使用continue：http://programmers.stackexchange.com/questions/58237/are-break-and-continue-bad-programming-practices - Rishi Dua

Answer 4

简单的O(nlogn)堆解法：

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

- Wilson Ng

Answer 5

我建议使用PriorityQueue，它是一个minmax head，时间复杂度为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;

}

你也可以使用Google Guava来实现这个功能（同样是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;
        }

仅仅比较这些Java实现与5百万条目的前10个，就可以得出结论：

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

- ixeption

Answer 6

这是我的解决方案。创建一个类，将索引与值配对：

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

在主方法中调用此类：

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

以及运行的示例输出：

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

我提供的例子只生成了值在0到99之间的十个整数，以便我能够看到它是否有效。您可以轻松更改此设置以适合任何大小的1000个值。另外，我没有运行三个单独的for循环，而是在添加到myArray后立即检查最新添加的值是否为最大值。试一下并看看它是否适用于您

- mistahenry

Answer 7

使用Arrays.sort(myArray)对数组进行排序，然后取最后5个元素。

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

如果需要索引，就没有像Python或其他语言那样的快速解决方案。您可以进行排序和扫描，但这很丑陋。

或者您可以采用面向对象的方式 - 毕竟这是Java。创建一个ArrayMaxFilter对象。它将具有一个私有类ArrayElement，其中包含索引和值，并具有按值自然排序的特性。它将具有一种方法，该方法接受一对int，即索引和值，创建它们的ArrayElement，并将它们放入长度为5的优先级队列中（或者您想要查找的任何数量）。提交来自数组的每个索引/值对，然后报告队列中剩余的值。(是的，传统上优先级队列保留最低值，但您可以在实现中翻转此值)

- Jon Kiparsky

---

OP希望保留原始数组中的索引。 - corsiKa

Answer 8

我的快速且有点“跳出常规思维”的想法是使用{{link1：EvictingQueue}}，它最多可以容纳5个元素。您需要使用数组中的前五个元素来预先填充它（按升序进行填充，因此您添加的第一个元素是这五个元素中最小的元素）。

然后，您必须遍历整个数组，并在当前值大于队列中最小值时向队列添加新元素。为了记住索引，创建一个包装对象（值/索引对）。

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

这是一个O(n)的解决方案。

- MarcelK

---

我的回答很相似 xD - nachokk