Efficient way to get indexes of matched items using Lists

I've two lists A and B. I'd like to find out indexes of elements in A that match elements of listB. Something like this:

ArrayList listA = new ArrayList();
listA.add(1);listA.add(2);listA.ad开发者_高级运维d(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);
   }
}

I guess that's one ugly way to doing it. What is the best way to finding all the indexes of A that match all elements in B? I believe there exists a method called containsAll in collections api - don't think it returns matching indexes.

---

If you had to use an ArrayList, you could create a HashSet from the ArrayList. This would make the call to contains O(1). It would take O(n) to create the HastSet. If you could start with a HashSet, that would be best.

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);
        }
    }   
}

---

The Guava libraries come with a method

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

that will give the elements contained in both sets, but not the indexes. Although it should be easy to get the indexes afterwards.

---

Simple:

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);
    }
}

But this only works if there is no repetition, if there are repeated indexes you have to do it the way you did, navigating the full list.

EDIT

I thought you wanted the elements, not indexes, sets are not going to give you indexes, only the elements.

---

Assuming there's no duplicate values, why not use 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);
            }
        }
    }
}

Output

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

---

If list A and list B are sorted in the same order (I'll assume ascending, but descending works as well) this problem has an O(n) solution. Below is some (informal, and untested) code. When the loop exits, indexMap should contain the indices of every element in list A that match an element in list B and the index of the matched element in list 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;
    }
  }

---

Using Apache CollectionUtils, there are plenty of options