java - 查找 List 中与某个元素相对应的所有索引的方法

Question

假设我有一个 long叫X和一个 List<Long>叫foo其中包含 X作为许多元素中的一个非唯一元素。我需要应用什么方法来查找 foo 中的所有索引对应于X 。这个foo不一定是排序的(但如果有一种需要排序的特定方法，一个好的答案可能会假设这一点 - 我对排序和未排序的情况都感兴趣)。

例如，这可能是设置问题:

long X = 5L
List<Long> foo = new ArrayList<Long>();
foo.add(4L);
foo.add(5L);
foo.add(5L);
foo.add(6L);
foo.add(7L);

我希望该方法接受 X作为参数并返回包含索引 1 的列表(或其他对象)和2 ，因为它们对应于 X 的位置foo内.

简单地说，

public static List<Long> locator(long target, List<Long> fooList) {
   List<Long> output = new ArrayList<Long>();

   for(int i = 0 ; i < foo.size() ; i++) {
      if(foo.get(i) == target) {
         output.add(i);
      }
   }

   return output;
}

但我想要一种更快的方法，以防我的 foo非常长。

Answer 1

如果列表已排序，请在遇到更大的内容后停止。如果列表实现允许随机访问(即 ArrayList )，则使用二分搜索。由于列表包含重复项，您需要从找到的元素向前和向后扫描，以确保获得所有索引。

如果搜索与更新的比率很大(搜索比更新多)，那么您可以在 Map<Long,List<Integer>> 中维护索引。它将每个值映射到该值出现在列表中的索引列表。当原始列表更新时，您将必须编写代码来维护索引。

在评估性能时，构建和维护索引的成本可以在搜索中摊销。如果列表创建后从未更新，并且搜索量很大，那么这将是明显的赢家。

但是，除非列表很大(> 10000)并且查询数量很大(> 1,000,000)，否则可能不值得这么麻烦。