java - 在 ArrayList 中查找所需数量的最小 double

Question

我有一个填充了 Double 值的 ArrayList，并且根据用户输入(一个 int)，我需要从此列表中找到输入的最小 Double 数量的索引。例如，如果用户输入 5，ArrayList 看起来就是这样(实际上要大得多):

-6789.44658
-27239.73827
-12365.78370
-456.789457
-4768.42579
-15263.26399
-15263.26399
-0.0
-24688.7289

我会得到1,5,8,2,6(5个最小的 double 从最小到最大的顺序并不重要)。这是我到目前为止所拥有的:

int[] indices = new int[input];
List<Double> copy = new ArrayList<Double>(origList); //origList is list of Doubles

for (int t = 0; t < input; t++)
{
    indices[t] = origList.indexOf(Collections.min(copy));
    copy.remove(Collections.min(copy));
}

但这有两个问题:

1. 效率确实很低
2. 在上面给出的 ArrayList 示例中，其中两个值是相同(甚至可能有三个相同的值)。如果相同的值是副本中的最低值，因为indexOf()返回该值在
   中第一次出现的索引origList，相同的索引返回两次。但是，没有一个指数可以是一样的。

感谢您的帮助!

Answer 1

一种解决方案是获取 origList 并在使用值填充 TreeMap<Double, List<Integer>> 后对其进行迭代。其中键是您的 double 值，列表是具有该值的索引列表。

当您向其中添加项目时，TreeMap 会保持顺序，因此无需执行额外的排序步骤。放入 TreeMap 的是 log(n)，因此查找最小的 n 个索引的时间应该是 O(log N)。

   int input = 5;
   List<Double> origList = new ArrayList<Double>();

   origList.add(-6789.44658);
   origList.add(-27239.73827);
   origList.add(-12365.78370);
   origList.add(-456.789457);
   origList.add(-4768.42579);
   origList.add(-15263.26399);
   origList.add(-15263.26399);
   origList.add(-0.0);
   origList.add(-24688.7289);

   TreeMap<Double, List<Integer>> smallest = new TreeMap<Double, List<Integer>>();
   for (int i = 0; i < origList.size(); i++) {
       double d = origList.get(i);
       List<Integer> list = smallest.get(d);
       if (list == null) {
           list = new ArrayList<Integer>();
           smallest.put(d, list);
       }
       list.add(i);
   }

现在您已经有了值到索引的排序映射，您只需从该映射中获取前 n 个键并获取它们的值即可。

   List<Integer> indices = new ArrayList<Integer>();

   for (Double key : smallest.keySet()) {
       List<Integer> list = smallest.get(key);
       for (Integer index : list) {
           indices.add(index);
           if (indices.size() == input) break;
       }
       if (indices.size() == input) break;
   }

   System.out.println(smallest);
   System.out.println(indices);

上面的代码生成以下 map :

{-27239.73827=[1], -24688.7289=[8], -15263.26399=[5, 6], -12365.7837=[2], -6789.44658=[0], -4768.42579=[4], -456.789457=[3], -0.0=[7]}

以及以下最终输出:

[1, 8, 5, 6, 2]