java - 从链表中删除集合的方法

标签 java methods collections linked-list hashset

我正在尝试创建一种方法,从链表“L1”中删除集合“L2”值的所有出现。我想知道该怎么做。目前我正在考虑从集合“L2”的值创建一个 HashSet 并将其删除,我只是想知道是否有一种方法可以使用 O(n) 的时间限制来创建该方法。

忘了说 Linkedlist L1 和 Collection L2 都没有排序。两者均由整数组成。

最佳答案

您可以在 L1 上使用 LinkedList.removeAll,在 L2 上使用 HashSet 如果它还不是一个哈希集:

L1.removeAll(L2 instanceof HashSet ? L2 : new HashSet<>(L2));

在更高层次上,这会迭代 L1 列表,如果它属于另一个集合 L2,则就地删除每个元素。

在内部,LinkedList.removeAll 使用它的 Iterator 遍历它的元素,然后使用另一个集合的 contains 方法来检查是否元素应该被删除。如果 contains 返回 true,它会通过 Iterator.remove 方法移除元素。

现在,在 LinkedList 上使用 Iterator.removeO(1) 最坏的情况,因为要删除的元素是当前指向的元素由迭代器。在 HashSet 上使用 containsO(1) 平均,所以整个解决方案要么是 O(n) 如果 L2 已经是一个 HashSet,或者 O(n+m) 如果不是。 (此处为 n=L1.size()m=L2.size())。

关于java - 从链表中删除集合的方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52745402/

相关文章:

java - Hibernate 和 Spring 注入(inject) Autowiring 依赖项的问题

objective-c - Ruby Motion 在 Ruby 中手动创建语法上类似 Objective-C 的函数

Java:方法在哪里?

.net - .NET 设计指南是否建议在 IEnumerable<T> 上返回 List<T>?

java - 是否可以使用 lambda 就地更改列表的值(无需创建新列表)?

java - 在 Eclipse 中更改左括号后下一行的缩进

java - 从 Java/Android 中的 URL 获取域名

java - 无法访问的声明?

c++ - 为什么 QList 不是从 QObject 派生的?

java - 云翻译API价格