如何在 Java 中快速对两个列表进行排序

Question

我有两个清单：List<Object1> list1 List<Object2> list2list1 对象包含一个 id。list2 对象包含一个 perId。我想从 list1 中删除所有匹配的对象Object1.id = Object2.perId.有没有人有办法快速做到这一点？

Answer 1

将perIds 中Object2的所有s收集到 a 中HashSet，然后从其list1id 在该集合中的所有元素中过滤掉：

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

这假设您的 id 是 type 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 是 list1 的长度，n 是 list2 的长度）

如果你关心时间复杂度。一种更快的方法是遍历 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 是 list1 的长度，n 是 list2 的长度）