如何计算C中两组之间的差异？
我有两个数组，比如说A和B，| A | = 8，| B | = 4。 我想计算设定差异AB。 我该怎么办？ 请注意，任何一组中都没有重复的元素。
编辑：非常感谢大家提供无数优雅的解决方案。 由于我处于项目的原型设计阶段，现在我实施了Brian和Owen所说的最简单的解决方案。 但我很欣赏你们其他人在这里建议的数据结构的巧妙使用，即使我不是计算机科学家而是工程师，从未将数据结构作为课程进行研究。 看起来是时候我应该真正开始阅读我一直拖延了很长一段时间的CLRS :)再次感谢！
迭代A的每个元素，如果每个元素都不在B中，则将它们添加到新的集合C.
排序数组A和B.
结果将在C中
让a – A的第一个元素
让b – B的第一个元素
然后：
1）当a
3）如果a = b：a = A的下一个元素，b = B的下一个元素
4）如果b结束：将A的剩余部分插入C并停止
5）如果结束：停止
这取决于你想要如何表示你的集合，但如果它们只是打包的那么你可以使用按位运算符，例如D = A & ~B; 如果集合适合整数类型，则会给出设置差异AB。 对于较大的集合，您可以使用整数类型的数组并迭代，例如
for (i = 0; i < N; ++i) { D[i] = A[i] & ~B[i]; }
以下假设集合存储为已排序容器（如std :: set所示）。
有一种常用的算法可以合并两个有序列表来生成第三个。 我们的想法是，当您查看两个列表的头部时，您可以确定哪个是较低的，提取它，并将其添加到输出的尾部，然后重复。
有些变体可以检测两个磁头相等的情况，并特别对待它。 设置交叉点和联合是这方面的例子。
对于设定的不对称差异，关键点是对于AB，当你提取B的头部时，你丢弃它。 当你提取A的头部时，你将它添加到输入中， 除非 B的头部相等，在这种情况下你也提取它并丢弃它们。
虽然这种方法是为顺序访问数据结构（和磁带存储等）而设计的，但对于随机访问数据结构来说，同样的事情是非常有用的，只要它无论如何顺序访问它都是合理有效的。 而且你不一定要真实地提取东西 – 你可以做复制和步骤。
关键点在于，您按顺序逐步执行输入，始终查看下一个最低剩余值，以便（如果输入没有重复），您将匹配项目。 因此，您始终知道您要处理的下一个最低值是A中的项目，B中没有匹配项目，B中项目A中没有匹配项目，或A项目中是否相等。
更一般地，用于设置差异的算法取决于集合的表示。 例如，如果将该集合表示为位向量，则上述将过复杂且缓慢 – 您只需循环执行按位运算的向量。 如果集合表示为哈希表（如在tr1 unordered_set中），则上述错误，因为它需要有序输入。
如果你有自己的二进制树代码用于集合，一个很好的选择是将两个树转换为链表，处理列表，然后将结果列表转换为完美平衡的树。 链表集差异非常简单，两次转换可重复用于其他类似操作。
编辑
关于复杂性 – 使用这些有序的类似合并算法的是O（n），前提是您可以在O（n）中进行有序遍历。 转换为列表并返回也是O（n），因为三个步骤中的每一个都是O（n） – 树到列表，设置差异和列表到树。
Tree-to-list基本上进行深度优先遍历，解析树的结构。 这是进行迭代的一个技巧，将“堆栈”存储在部分处理的节点中 – 在您步入左子节点之前将左子指针更改为父指针。 如果树可能很大且不平衡，这是一个好主意。
将列表转换为树基本上包括对假想树进行深度优先遍历（基于大小，从一开始就知道），将其构建为真实的。 例如，如果一棵树有5个节点，你可以说根将是节点3.你试图建立一个双节点左子树，然后从列表中获取该根的下一个项，然后递归建立一个 – 节点右子树。
列表到树的转换不需要迭代实现 – 递归很好，因为结果总是完美平衡。 如果你无法处理log n递归深度，你几乎肯定无法处理整个树。
在C中实现一个set对象。您可以使用底层存储的哈希表来完成它。 这显然是一项非常重要的工作，但存在一些开源解决方案。 然后，您只需要添加A的所有元素，然后迭代B并删除任何元素。
关键是为作业使用正确的数据结构。
对于较大的集合，我建议对数字进行排序并通过模拟http://www.cplusplus.com/reference/algorithm/set_difference/上的代码来迭代它们，这些代码将是O（N * logN），但是因为设置的大小如果这么小，Brian给出的解决方案看起来很好，即使它理论上在O（N ^ 2）处较慢。