Python，计算数组元素数量的确切差异

Question

我在 Python 中有两个列表，如下所示：

temp1 = ['A', 'A', 'A', 'B', 'C', 'C','C']
temp2 = ['A','B','C','C']

我需要用第一个列表中的项目创建第三个列表，这将与 temp2 中存在的元素的确切数量不同，我需要在下面创建：

temp3 = ['A','A','C']

最好的方法是什么？使用集合没有按预期工作，所以现在想知道有没有一种快速的方法可以使用 python 标准函数或者我必须创建自己的函数？

Answer 1

temp1 = ['A', 'A', 'A', 'B', 'C', 'C','C']
temp2 = ['A','B','C','C']
# create a copy of your first list
temp3 = list(temp1)
# remove every item from the second list of the copy
for e in temp2:
    temp3.remove(e)

输出：

['A', 'A', 'C']

Answer 2

如果保证对列表进行排序，就时间复杂度而言，您可以比 list.remove 或使用以下方法计算每次迭代做得更好：

temp1 = ['A', 'A', 'A', 'B', 'C', 'C', 'C']
temp2 = ['A', 'B', 'C', 'C']

filtered = []
j = 0
for i, letter in enumerate(temp1):
    while j < len(temp2) and temp2[j] < letter:
        j += 1
    if j == len(temp2):
        break

    if temp2[j] > letter:
        filtered.append(letter)
    else:
        j += 1

filtered.extend(temp1[i:])

另一种解决方案

我想到的一个比较有意思的方案：

from collections import Counter
result = []
for letter, count in (Counter(temp1)-Counter(temp2)).items():
    result.extend([letter]*count)

这是和上面一样的大O复杂度。

如果列表未排序

如果顺序不重要，这些解决方案仍然要快得多，因为对列表进行排序比 O(n^2) 解决方案成本更低，而第二个甚至不需要它。如果是，这仍然有效，您只需要在排序之前保留 element->index 的映射（您的 temp1 已经是），尽管这可能超出了这个问题的范围。

Answer 3

你可以试试

temp1 = ['A', 'A', 'A', 'B', 'C', 'C','C']
temp2 = ['A','B','C','C']
temp3 = []

for i in temp1:
    if temp1.count(i) - temp2.count(i) > temp3.count(i):
        temp3.append(i)
print(temp3)

此代码将检查是否在 temp3 中初始化了所有 diff 元素，如果没有，它将把相关的 temp1 项目附加到 temp3 列表中。

输出

['A', 'A', 'C']

Answer 4

from collections import Counter

temp1 = ['A', 'A', 'A', 'B', 'C', 'C', 'C']
temp2 = ['A', 'B', 'C', 'C']

result = []

counts = Counter(temp2)

for item in temp1:
    if item in counts and counts[item]:
        counts[item] -= 1
    else:
        result.append(item)

print(result)

输出：

['A', 'A', 'C']

缩放 O(n) 并且不依赖于排序的输入。

这个答案依赖于 Counter 只是 dict 的子类这一事实，因此我们可以将实例用作可变对象，在其中存储 [=14] 中出现的次数=] 我们仍然需要在 temp1 的迭代期间从结果中排除。 documentation 明确指出“Counter 是一个 dict 子类”并且“Counter 对象有一个字典接口”，这很好地保证了项目分配将是支持，并且没有必要将其视为只读对象，必须首先将其复制到普通 dict.

Python，计算数组元素数量的确切差异

Python, compute array difference in exact amount of elements

python

arrays

diff