根据其他列表中的Id匹配从列表中删除对象

Question

我有一个对象列表List<A> list1... A有两个成员id和name......现在我还有一个列表List<Integer> list2只包含id...我需要删除其id不存在的所有A对象.list1list2

到目前为止我尝试了什么:

void removeUnwanted(List<A> a, List<Integer> b) {
    for (A object : a) {
        if (!(b.contains(object.id))) {
            b.remove(object)
        }
    }
}

任何人都可以帮我建议最有效的方法吗？

Answer 1

您应该将id添加到一个集合中以进行快速搜索,然后遍历列表并删除不在id集合中的ID:

Set<Integer> ids = new HashSet<Integer>(list2);
Iterator<A> it = list1.iterator();
while (it.hasNext()) {
    if (!ids.contains(it.next().id)) {
        it.remove();
    }
}

Answer 2

通过创建一个键是 ID、值是对象的对象，可以在O(n)时间（一般情况）和空间上完成此操作。HashMap<Integer,A>A

现在，迭代列表list2并仅生成A具有与 中某些 id 匹配的键的值（对象）list2。

类似java的伪代码：

Map<Integer,A> map = new HashMap<>();
for (A a : list1) map.put(a.id,a);
for (int id : list2) { 
   A a = map.get(id);
   //do something with a, maybe populate a new list
}

另一种方法是对两个列表进行排序，并并行迭代，同时丢弃没有匹配 id 的元素。这给出了 O(nlogn) 时间（最坏情况）和 O(1) 空间：

高级伪代码：

sort(list1) //according to id
sort(list2)
iter1 = 0
iter2 = 0
while (iter1<list1.size() && iter2<list2.size()) { 
   int id = list1.get(iter1).id
   if (id < list2.get(iter2)) { //discard and advance the smaller one
       list1.remove(iter1) //can be done efficiently if the list is linked list

   } else if (id == list2.get(iter2)) { //advance both, element should remain in list1
      iter1++; iter2++;
   } else { //advance iter2
      iter2++;
   }
}