在常量时间内通过索引从列表中获取多个元素

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),它在所请求的元素数量(长度indices)中是线性的,但不会随着列表的长度而增加list.正如评论中所讨论的那样,这是我们能做的最好的事情.

编辑:老实说我不知道​​上面的收集步骤是否在收集元素数量的线性时间内.可能是列表容量成本增加的时间延长,并且这可能不会超过线性时间.如果我们需要确定,我们需要采用这种方式:

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

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