在Python中高效地从列表中删除给定列表中的元素

Question

我有两个列表和一个主列表，如果主列表中的元素存在于另外两个列表中的任意一个中，那么需要将其移除。

例如：

s1 = [1,2,3,4,7]
s2 = [3,4,5,6,20]
mainlist = [6,7,8,9,10,11,12,13,14,15]

因此，由于主列表包含元素6和7，这些元素也存在于s1或s2中，它们应该被移除，结果应如下所示。

resultList = [8,9,10,11,12,13,14,15]

我的代码：

for j in mainlist[:]:
    if j in s1 or j in s2:
        mainlist.remove(j)

有没有不使用for循环的方法？我需要一种高效的方式来降低时间复杂度。谢谢！

- Suhail Pappu

---

你可以使用列表推导式，但时间复杂度仍然是问题固有的属性。 - quamrana

谢谢大家，我已经尝试了所有的解决方案，但仍然出现了超时错误。 - Suhail Pappu

Answer 1

您可以使用列表推导式，它非常适合解决这种问题：

result = [x for x in mainlist if x not in s1 and x not in s2]

使用列表/集合操作，您可以执行以下操作之一：

result = list(set(mainlist) - (set(s1) | set(s2)))  # remove the concat of s1&s2
result = list(set(mainlist) - set(s1) - set(s2))    # remove s1 and s2

- azro

Answer 2

也许您可以使用列表推导式创建另一个列表

res = [i for i in test_list if i not in s1 and i not in s2]

或者使用 filter() + lambda

res = filter(lambda i: i not in s1 and i not in s2, mainlist) 

或者使用 for 循环

for elem in mainlist:
   if elem in s1 or elem in s2:
      mainlist.remove(elem)

- Ryuzaki L

---

谢谢大家，我已经尝试了所有的解决方案，但仍然出现了超时错误。 - Suhail Pappu

@SuhailPappu，你完成这个任务的时间框架是多久？ - Ryuzaki L

我不知道这是一个在线比赛。 - Suhail Pappu

Answer 3

你可以将 s1 和 s2 转换为 dict。

s1 = {i:i for i in s1}
s2 = {i:i for i in s2}
mainlist = [i for i in mainlist if i not in s1 or i not in s2]

你将花费一些时间将列表转换为字典，但由于Python字典基本上是哈希表，因此搜索复杂度为 O(1) ，而不像列表那样是 O(n) 。所以最终它不会是 O(n^2) ，而是类似于 O(n) 的复杂度。如果你尝试了这个方法，请告诉我。

- music_junkie

---

@SuhailPappu 你尝试过不使用列表切片吗？ - music_junkie

@SuhailPappu 你可以请编辑你的问题，并附上这段代码吗？ - music_junkie

Answer 4

试试这个：

mainlist = list(set(mainlist) - (set(s1)|set(s2)))

在这里，我假设没有重复元素存在于任何列表中。

您可以计时并与其他方法进行比较。

time_idx = time()
result = [x for x in mainlist if x not in s1 and x not in s2]
print(time() - time_idx)

0.00012612342834472656

time_idx = time()
mainlist = list(set(mainlist) - (set(s1)|set(s2)))
print(time() - time_idx)

0.00010609626770019531

改进非常显著，因为这是一个小列表。

- Akash Kumar

Answer 5

只需使用集合操作进行过滤

>>> list(set(mainlist) - set(s1+s2))
>>> [8, 9, 10, 11, 12, 13, 14, 15]

- Saleem Ali

Answer 6

你也可以使用计数器来执行这个操作：

from collections import Counter

print(list(Counter(mainlist) - Counter(s1) - Counter(s2)))
Out[309]: [8, 9, 10, 11, 12, 13, 14, 15]

- oppressionslayer