Geek Answers Handbook

Efficient way to get matching item indices using lists

I have two lists A and B. I would like to find the indices of the elements in A that match the elements of listB. Something like that:

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

I guess one ugly way to do this. What is the best way to find all indices A that match all elements in B? I believe that there is a method called containsAll in api collections - I don't think it returns the corresponding indexes.

+4
source share
6 answers

If you need to use an ArrayList , you can create a HashSet from an ArrayList . This will call contains O (1). To create a HastSet need O (n). If you could start with a HashSet , that would be better.

 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); } } }
+3
source

Guava libraries have a method

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

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

+2
source

Plain:

 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 duplicate indexes that you must do as you did by going to the full list.

EDIT

I thought you needed elements, not indexes; sets will not give you indexes, but only elements.

+1
source

Assuming there are 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
+1
source

If list A and list B are sorted in the same order (I will consider ascending, but the descent also works), this problem has a solution O (n). Below is some (informal and unverified) code. When the loop exits, indexMap should contain the indices of each element in list A, which correspond to the element in list B and the index of the associated 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;
     }
   }
+1
source

Using Apache CollectionUtils , there are many options

0
source

More articles:


All Articles