时间戳

首页 > 解决方案 > 如何在 Java 中快速对两个列表进行排序

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

问题描述

我有两个清单：

List<Object1> list1
List<Object2> list2

我想从 list1 中删除所有匹配的对象

Object1.id = Object2.perId.

有没有人有办法快速做到这一点？

标签： javalistsorting

解决方案

使用集合在 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 的长度）

推荐阅读