Как быстро отсортировать два списка в Java

Question

У меня есть два списка:

List<Object1> list1
List<Object2> list2

• объект list1 содержит идентификатор.
• объект list2 содержит perId.

Я хочуудалить из списка1 все объекты, которые соответствуют

Object1.id = Object2.perId.

У кого-нибудь есть способ сделать это быстро?

Answer 1

Соберите все perId s из Object2 s в HashSet, а затем отфильтруйте из list1 всех элементов, чей идентификатор находится в этом наборе:

Set<Integer> ids = list2.stream()
        .map(x -> x.perId)
        .collect(toCollection(HashSet::new));
List<Object1> result = list1.stream()
        .filter(x -> !ids.contains(x.id))
        .collect(toList());

Это предполагает, что ваш идентификаторимеет тип int, поэтому вы можете изменить его соответствующим образом.

Для этого решения не требуется, чтобы у ваших двух классов Object1 и Object2 были методы equals() или hashCode().

Answer 2

Быстрая сортировка списков в Java с использованием коллекций.

Collections.sort(list1);
Collections.sort(list2);

Если вы сравниваете значения после сортировки:

for (Object1 o : list1) {
  for (Object2 p : list2) {
     if ((o.getSomeValue()).equals(p.getSomeValue())) list1.remove(o);
  }
}

Сложность по времени будет mxn для этого.(где m - длина списка 1, а n - длина списка 2)

Если вас волнует сложность времени.Более быстрым способом было бы перебирать list2 и добавлять каждое значение в HashSet.Затем выполните отдельный цикл по list1 и сравните значения со значениями, которые мы имели в HashSet.По сути, это должно выглядеть так, но вы должны добиться прогресса с помощью своего кода.

HashSet<T> hSet = new HashSet<T>(); 

for (Object2 p : list2) {
   if (!hSet.contains(p.getSomeValue())) {
      hSet.add(p);
   } 
}

for (Object1 o : list1) {
   if (hSet.contains(o.getSomeValue())) {
      list1.remove(o);
   } 
}

Сложность по времени = m + n (где m - длина списка 1, а n - длина списка 2)