使用列表获取匹配项索引的有效方法

Question

我有两个列表 A 和 B。我想找出 A 中与 listB 元素匹配的元素的索引。像这样的事情：

ArrayList listA = new ArrayList();
listA.add(1);listA.add(2);listA.add(3);listA.add(4);
ArrayList listB = new ArrayList();
listB.add(2);listB.add(4);
ArrayList listC = new ArrayList();
for(int i=0; i<listB.size();i++) {
   int element = listB.get(i);
   for(int j=0; j<listA.size(); j++) {
      if(listA.get(j) == element) listC.add(j);
   }
}

我想这是一种丑陋的做法。查找 A 中与 B 中所有元素匹配的所有索引的最佳方法是什么？我相信集合 api 中存在一个名为 containsAll 的方法 - 不认为它返回匹配的索引。

Answer 1

如果您必须使用ArrayList，您可以从ArrayList 创建一个HashSet。这将使对 contains 的调用 O(1)。创建 HastSet 需要 O(n) 时间。如果您可以从 HashSet 开始，那就最好了。

public static void main(String[] args) 
{
    List listA = new ArrayList();
    listA.add(1);
    listA.add(2);
    listA.add(3);
    listA.add(4);
    List listB = new ArrayList();
    listB.add(2);
    listB.add(4);
    Set hashset = new HashSet(listA);

    for(int i = 0; i < listB.size(); i++) 
    {
        if(hashset.contains(listB.get(i))) 
        {
            listC.add(i);
            System.out.println(i);
        }
    }   
}

Answer 2

Guava 库提供了一种方法

"SetView com.google.common.collect.Sets.intersection(Set a, Set b)

，可以提供两个集合中包含的元素，但不提供索引。虽然之后应该很容易获得索引。

Answer 3

简单：

List<Integer> listA = new ArrayList<Integer>();
listA.add(1);
listA.add(2);
listA.add(3);
listA.add(4);

List<Integer> listB = new ArrayList<Integer>();
listB.add(2);
listB.add(4);

List<Integer> listC = new ArrayList<Integer>();

for ( Integer item : listA ) {
    int index = listB.indexOf( item );
    if ( index >= 0 ) {
        listC.add(index);
    }
}

但这仅在没有重复的情况下有效，如果有重复的索引，您必须按照您的方式进行操作，导航完整列表。

编辑

我以为你想要元素，而不是索引，集合不会给你索引，只会给你元素。

Answer 4

假设没有重复值，为什么不使用 ArrayList.indexOf？

---

public final class ArrayListDemo {
    public static void main(String[]args){
        findIndices(createListA(), createListB());      
    }

    private static final List<Integer> createListA(){
        List<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(3);
        list.add(5);

        return list;
    }

    private static final List<Integer> createListB(){
        List<Integer> list = new ArrayList<Integer>();
        list.add(0);
        list.add(2);
        list.add(3);
        list.add(4);

        return list;
    }

    private static void findIndices(List<Integer> listA, List<Integer> listB){
        for(int i = 0; i < listA.size(); i++){  
            // Get index of object in list b
            int index = listB.indexOf(listA.get(i));

            // Check for match
            if(index != -1){
                System.out.println("Found match:");
                System.out.println("List A index = " + i);
                System.out.println("List B index = " + index);
            }
        }
    }
}

输出

Found match:
List A index = 1
List B index = 2

Answer 5

如果列表 A 和列表 B 按相同的顺序排序（我假设升序，但降序也有效），这个问题有一个 O(n) 解决方案。下面是一些（非正式的、未经测试的）代码。当循环退出时，indexMap 应包含列表 A 中与列表 B 中的元素匹配的每个元素的索引以及列表 B 中匹配元素的索引。

  int currentA;
  int currentB;
  int listAIndex = 0;
  int listBIndex = 0;
  Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();

  currentA = listA.get(listAIndex);
  currentB = listB.get(listBIndex);
  while ((listAIndex < listA.length) && (listBIndex < listB.length))
  {
    if (currentA == currentB)
    {
      indexMap.put(listAIndex, listBIndex);
      ++listAIndex;
    }
    else if (currentA < currentB)
    {
      ++listAIndex;
    }
    else // if (currentA > currentB)
    {
      ++listBIndex;
    }
  }

Answer 6

使用 Apache CollectionUtils，有很多选项