java - 排序后获取未排序 double 组的索引

Question

这个问题是与此 one 一起提出的。这被视为 double 组的最快排序。

现在我想获取与未排序数组对应的 top-k 索引。

我已经实现了这个版本，它(不幸的是)使用了自动装箱和HashMap，正如一些答案中所建议的，包括这个one :

HashMap<Double, Integer> map = new HashMap<Double, Integer>();
for(int i = 0; i < numClusters; i++) {
    map.put(scores[i], i);
}
Arrays.sort(scores);
HashSet<Integer> topPossibleClusters = new HashSet<Integer>();
for(int i = 0; i < numClusters; i++) {
    topPossibleClusters.add(map.get(scores[numClusters - (i+1)]));
}

正如您所看到的，它使用一个 HashMap，其键是原始数组的 Double 值，值是原始数组的索引。 因此，在对原始数组进行排序后，我只需从 map 中检索它。

我还使用 HashSet，因为我有兴趣使用 .contains() 方法确定此集合中是否包含 int。 (我不知道这是否有影响，因为正如我在另一个问题中提到的，我的数组很小 -50 个元素)。如果这没有什么区别，请指出。

我对值(value)本身不感兴趣，只对指数感兴趣。

我的问题是是否有更快的方法来配合它？

Answer 1

这种相互链接/互锁的集合本身就导致了脆弱、容易损坏、难以调试、无法维护的代码。

而是创建一个对象:

class Data {
    double value;
    int originalIndex;
}

创建存储原始值和索引的 Data 对象数组。

使用自定义比较器对它们进行排序，该比较器查看 data.value 并按降序排序。

现在，数组中的前 X 项就是您想要的项，您只需根据需要查看 value 和 originalIndex 即可。