Эффективный способ получить индексы совпадающих элементов, используя списки

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, вы могли бы создать HashSet из ArrayList.Это вызовет 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

Если список 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 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

Простой:

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 6

Использование Apache CollectionUtils , существует множество вариантов