algorithm - 之前和之后的集合发生了什么变化

Question

这是一道面试题:给你两个数组:之前:{3, 3, 5, 8, 1} 和之后:{5, 3, 2, 4}。确定从“之前”数组中删除/添加了哪些数字以获得“之后”。

我可以考虑为每个列表使用两个 HashMap ，并比较每个列表以判断每个元素是否已添加或删除。

有人可以为此想出更好的方法或提供替代解决方案(具有更好的时间/空间复杂性)吗？

Answer 1

您可以将每个列表存储在 bags 中，然后找到 bags 中每种项目类型出现次数的变化。

这是一些 Python:

>>> # Original data
... l1, l2 = [3,3,5,8,1], [5,3,2,4]
>>> # Pythons Counter class in also known as a bag
... from collections import Counter
>>> c1, c2 = Counter(l1), Counter(l2)
>>> # Quick calculation
... diffs = {item:(c2[item] - c1[item]) for item in set(c1) | set(c2)}
>>> diffs
{1: -1, 2: 1, 3: -1, 4: 1, 5: 0, 8: -1}
>>> # Or if you want it wordy
... for item in sorted(set(c1) | set(c2)):
...     print('Item %i changed its occurences by %2i'
...           % (item, c2[item] - c1[item]))
... 
Item 1 changed its occurences by -1
Item 2 changed its occurences by  1
Item 3 changed its occurences by -1
Item 4 changed its occurences by  1
Item 5 changed its occurences by  0
Item 8 changed its occurences by -1
>>>