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

}

您还可以采取其他措施来减少此操作的开销.例如,您可以选择使用仅跟踪最大5的队列而不是排序.因为int它们的值可能必须被加框以添加到集合中(除非您自己滚动),这显着增加了开销.

Answer 2

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

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

因此我实施了它：

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