我正在尝试创建一种方法,从链表“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.remove
是 O(1)
最坏的情况,因为要删除的元素是当前指向的元素由迭代器。在 HashSet
上使用 contains
是 O(1)
平均,所以整个解决方案要么是 O(n)
如果 L2
已经是一个 HashSet
,或者 O(n+m)
如果不是。 (此处为 n=L1.size()
和 m=L2.size()
)。
关于java - 从链表中删除集合的方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52745402/