在O(n)时间复杂性中删除两个列表中的公共元素

Question

假设我的两个列表：

a=[1,1,2,2,3,3]
b=[1,2,3,4]

所以，我得到的列表应该是

a1=[1,2,3]
b1=[4]

请帮助

Answer 1

以下是如何使用列表综合：

a=[1,1,2,2,3,3]
b=[1,2,3,4]
a1 = [v for i,v in enumerate(a) if v not in a[:i]]
b1 = [v for v in b if v not in a]

您可以使用Jan答案中的集合，但是，您将无法根据索引从数组中检索元素此代码保持订单

Answer 2

在它们上使用sets(...)和-：

a = [1, 1, 2, 2, 3, 3]
b = [1, 2, 3, 4]
a, b = map(set, [a, b])
b = b - a
print(a, b)

这产生

{1, 2, 3} {4}

Answer 3

你可以使用简单的if检查来检查下面的

a=[1,1,2,2,3,3]
b=[1,2,3,4]
x=[]
y=[]
for i in a:
if i not in x:
x.append (i)
for i in b:
if i not in x and i not in y:
y.append(i)
print(x,y)

Answer 4

您可以使用set()，但它可能无法维持秩序。

a = [1,1,2,2,3,3]
b = [1,2,3,4]
a1 = list( set(a) & set(b) )
b1 = list( set(a) ^ set(b) )
print(a1)
print(b1)

Answer 5

1. 构建dict计数元素发生
2. 查找出现次数的差异
3. 填充出现次数不同的最终列表
   a。不保留顺序的版本只会重复元素差异时间
   b。保留顺序的版本为每次出现递减计数器，如果计数器为0或更小，则过滤掉元素
   (例如：元素'4'在a中出现2次，但在b中出现3次，diff为-1，不保留任何'4'。但是，如果6次和3次，则diff为3，则保留3x'4'(

不保留订单的版本：

import collections
a=[1,1,2,2,3,3]
b=[1,2,3,4]
# element counter O(n)
ac = collections.Counter(a)
bc = collections.Counter(b)
# union of all keys in dict O(n)
keys = set(ac) | set(bc)
# get difference for all counters O(n)
diff = {k: ac.get(k,0)-bc.get(k,0) for k in keys}
a1 = []
b1 = []
# iterate over all keys O(n)
for k,v in diff.items():
a1+=[k]*v
b1+=[k]*-v
# concatenate to lists, repeat element v times
print(a1,b1)

订单保存版本：

import collections
a=[1,1,2,2,3,3]
b=[1,2,3,4]
# element counter O(n)
ac = collections.Counter(a)
bc = collections.Counter(b)
# get difference for all counters O(n)
diffa = {k: v-bc.get(k,0) for k,v in ac.items()}
diffb = {k: v-ac.get(k,0) for k,v in bc.items()}
a1 = []
b1 = []
# iterate over all keys O(n)
for x in a:
if(diffa[x]>0):
a1 += [x]
diffa[x] -= 1
for x in b:
if(diffb[x]>0):
b1 += [x]
diffb[x] -= 1
print(a1,b1)

注意：这对于通过构建查找表(更不用说考虑空间复杂性(来保持复杂性线性O(n(具有较高的开销成本。它大约在O(6n(左右，所以只有当列表非常大时才有性能优势。对于像OP中的例子这样的小列表；在"；由于不必创建查找表，因此对每个元素的查找将更快
如果这不是针对编码挑战，那么您可能应该使用不同的方法处理数据，或者这里的复杂性优势不适用于您。如果是针对某种大数据处理类型的任务，您的瓶颈可能是正确使用生成器和缓冲/分割IO，而您的框架已经有了更好的方法来处理这些问题。