查找列表中与<Long>某个元素对应的所有索引的方法

Question

假设我有一个名为X的long和一个名为foo的List<Long>，它包含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的列表（或其他对象），因为它们对应于foo中X的位置。

微不足道，

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），否则可能不值得麻烦。

Answer 2

如果使用 GS 集合，则可以对源列表和索引列表使用基元列表，因此不会产生对基元值进行装箱的成本。 以下代码将在 Java 8 中使用 lambda 与您的示例一起工作：

long X = 5L;
LongArrayList list = LongArrayList.newListWith(4L, 5L, 5L, 6L, 7L);
IntArrayList indices = new IntArrayList();
list.forEachWithIndex((each, index) -> { if (each == X) indices.add(index);});
Assert.assertEquals(IntArrayList.newListWith(1, 2), indices);   

在Java 7中，它如下所示：

long X = 5L;
LongArrayList list = LongArrayList.newListWith(4L, 5L, 5L, 6L, 7L);
IntArrayList indices = new IntArrayList();
list.forEachWithIndex(new LongIntProcedure() 
{
    public void value(long each, int index) 
    {
        if (each == X) indices.add(index);
    }
});
Assert.assertEquals(IntArrayList.newListWith(1, 2), indices);

注意：我是 GS 集合的开发人员。

Answer 3

试试这个解决方案：

int firstIndex = foo.indexOf(X);
int count = Collections.frequency(foo, X);

如果您的List已排序，则您有 2 个位置：firstIndex 和 firstIndex + 1

从您的示例中：

long X = 5L
List<Long> foo = new ArrayList<Long>();
foo.add(4L);
foo.add(5L);
foo.add(5L);
foo.add(6L);
foo.add(7L);
int firstIndex = foo.indexOf(X); // 1
int count = Collections.frequency(foo, X); // 2
List<Long> output = new ArrayList<Long>();
for(int i=firstIndex; i<count; i++ ){
  output.add(i);
}