java - 查找数组中 k 个最小数字的索引的算法

Question

考虑如下情况:

数组 amounts 跟踪一些统计数量:

int[] amounts = { 1, 2, 5, 7, 2, 4, 8, 6 };

众所周知，数组将始终具有固定大小(在本例中为 8)。我需要找到的是给定数目 k 的最小元素的 indexes:

int   k = 5;
int[] smallest = { 1, 2, 2, 4, 5 };
int[] smallestIndices = { 0, 1, 4, 5, 2 };

我想我可以利用 Selection Algorithm ，但我意识到这会重新排序数组，从而返回不正确的索引。

我想出的另一个想法是创建一个索引和值元组数组，然后按元组值对该数组进行排序。然后我可以提取排序数组中前 k 元组的索引。然而，这似乎是一个浪费的解决方案，但可能更容易完成。

是否有一种算法可以让我在大小为 n 的数组中找到 k 最小数字的索引？

• 请注意，我不是在寻找最小的 k numbers，这已由 this question 回答.我正在寻找他们的索引。因此，不应将此问题标记为重复问题。

Answer 1

创建一个索引数组，即数组 [0,n)，按位于主数组中该索引处的元素排序。现在您需要做的就是从索引数组中取出顶部元素。

没有必要使用对。

具体例子:

//imports
import static java.util.Comparator.comparing;

//method
public static int[] bottomN(final int[] input, final int n) {
    return IntStream.range(0, input.length)
            .boxed()
            .sorted(comparing(i -> input[i]))
            .mapToInt(i -> i)
            .limit(n)
            .toArray();
}

用法:

public static void main(String[] args) throws Exception {
    int[] amounts = {1, 2, 5, 7, 2, 4, 8, 6};
    System.out.println(Arrays.toString(bottomN(amounts, 5)));
}

输出:

 [0, 1, 4, 5, 2]

所以我们所做的就是获取数组 [0,1,2,3,4,5,6,8] 然后根据输入数组中元素的值对它进行排序等于当前数组元素的索引。这将使用一个索引数组，这些索引按输入中的值排序。

最后我们修剪顶部的 n 并返回它。