假设我有一个 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
非常长。
最佳答案
如果列表已排序,请在遇到更大的内容后停止。如果列表实现允许随机访问(即 ArrayList
),则使用二分搜索。由于列表包含重复项,您需要从找到的元素向前和向后扫描,以确保获得所有索引。
如果搜索与更新的比率很大(搜索比更新多),那么您可以在 Map<Long,List<Integer>>
中维护索引。它将每个值映射到该值出现在列表中的索引列表。当原始列表更新时,您将必须编写代码来维护索引。
在评估性能时,构建和维护索引的成本可以在搜索中摊销。如果列表创建后从未更新,并且搜索量很大,那么这将是明显的赢家。
但是,除非列表很大(> 10000)并且查询数量很大(> 1,000,000),否则可能不值得这么麻烦。
关于java - 查找 List<Long> 中与某个元素相对应的所有索引的方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19206748/