algorithm - 查找一组中存在的元素而不是另一组中存在的元素

Question

我有两套A和B。

A
--
1
2
6

B
--
1
2
3
4

当我将集合 A 与 B 进行比较时，我需要将值 6 作为输出，将集合 B 与 A 进行比较时将值 4 作为输出。

我想知道执行此操作的最佳算法是什么？我已经写了一个，但它有一个二次复杂度。它基本上迭代一组并在循环内迭代第二组以检查值是否存在。我觉得这很低效。

上下文

我在 UI 中显示的数据库中有一组值。用户可以在列表中删除或添加新项目，然后按“保存更改”按钮，这会将所有更改保存到数据库中。所以在这里我需要将新添加的项目插入数据库并删除删除的项目。

所以我通过了第一组，其中包含新添加的和已经存在的项目。我加载另一组，它将包含数据库中的所有项目。现在，如果我应用上述算法来比较集合 A(新列表)和集合 B(数据库列表)并获取存在于 SetA 中而不存在于 SetB 中的项目，我将获得所有新添加的项目。然后将 SetB 与 SetA 进行比较，所有存在于 setB 中且不存在于 SetA 中的项目将被删除。我乐于接受有关更好算法的建议。

任何帮助都会很棒。

Answer 1

在 Python 中

>>> A=set((1,2,6))
>>> B=set((1,2,3,4))
>>> A-B
set([6])
>>> B-A
set([3, 4])

假设你没有内置的集合类型
伪代码:

# This computes the items of B that are not in A
a=hash(A)   # Hopefully you at least have some sort of hash type
result=[]   #empty list
for item in B:
    if item not in a:
        result.append(item)