java - 在常数时间内按索引从列表中获取多个元素

Question

在恒定时间内通过索引从列表中获取多个元素的最佳方法是什么？

如果我有一个数组:

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("e");

我有一个带索引的列表/数组:

List<Integer> indices = new ArrayList<>();
indices.add(0);
indices.add(2);
indices.add(3);

如何在常数时间内得到 a,c,d？我需要这样的东西:

List<String> filtered = list.filterByIndex(indices);
filtered.stream().forEach(x -> System.out.print(x));
// output:"acd"

更新:当然，项目的打印不必在恒定时间内进行，只需收集项目即可。上面打印元素的代码仅用于演示目的。

Answer 1

我建议:

    List<String> filtered = indices.stream()
            .map(list::get)
            .collect(Collectors.toList());

结果如愿:

[a, c, d]

假设列表具有恒定时间访问(如 ArrayList 具有)，它的运行时间与请求的元素数量(索引 的长度)成线性关系, 但不随列表 list 的长度增加。正如评论中所讨论的那样，这是我们能做的最好的事情。

编辑:老实说，我不知道上面的收集步骤是否与收集的元素数量成线性时间。列表容量的扩展可能会花费时间，而且可能不会超过线性时间。如果我们需要确定，我们需要以这种方式收集:

            .collect(Collectors.toCollection(() -> new ArrayList<>(indices.size())));

这可确保从一开始就分配具有适当容量的列表，因此不需要扩展。