如何计算C中两组之间的差异？

Question

我有两个数组,比如说A和B,| A | = 8,| B | = 4.我想计算设定差异AB.我该怎么办？请注意,其中任何一组都没有重复的元素.

编辑:非常感谢大家提供无数优雅的解决方案.由于我处于项目的原型设计阶段,现在我实施了Brian和Owen所说的最简单的解决方案.但我很欣赏你们其他人在这里建议的数据结构的巧妙使用,即使我不是计算机科学家而是工程师,从未将数据结构作为课程进行研究.看起来是时候我应该真正开始阅读CLRS了,我拖延了很长一段时间:)再次感谢!

Answer 1

排序数组A和B的
结果将是C
let a - A的第一个元素
b - B的第一个元素
然后:
1)而a <b:将a插入C和a = A
2的下一个元素) > b:b = B的下一个元素
3)如果a = b:a = A的下一个元素,b = B的下一个元素
4)如果b结束:将A的剩余部分插入C并停止
5)如果a去结束:停止

Answer 2

迭代A的每个元素,如果每个元素都不在B中,则将它们添加到新的集合C.

Answer 3

这取决于你想要如何表示你的集合,但如果它们只是打包的那么你可以使用按位运算符,例如D = A & ~B;,如果集合适合整数类型,它会给你设置差异AB.对于较大的集合,您可以使用整数类型的数组并迭代,例如

for (i = 0; i < N; ++i)
{
    D[i] = A[i] & ~B[i];
}

Answer 4

以下假设集合存储为已排序的容器(如std :: set所示).

有一种通用的算法可以合并两个有序列表来生成第三个.我们的想法是,当您查看两个列表的头部时,您可以确定哪个是较低的,提取它,并将其添加到输出的尾部,然后重复.

有些变体可以检测出两个磁头相等的情况,并特别对待它.设置交叉点和联合是这方面的例子.

对于设定的不对称差异,关键点是对于AB,当你提取B的头部时,你丢弃它.当你提取A的头部时,你将它添加到输入中,除非 B的头部相等,在这种情况下你也提取它并丢弃它们.

虽然这种方法是为顺序访问数据结构(和磁带存储等)而设计的,但对于随机访问数据结构来说,同样的事情是非常有用的,只要它无论如何顺序访问它都是合理有效的.而且你不一定要真实地提取东西 - 你可以做复制和步骤.

关键点在于您按顺序逐步执行输入,始终查看下一个最低剩余值,以便(如果输入没有重复),您将匹配项目.因此,您始终知道您要处理的下一个最低值是A中的项目,B中没有匹配项目,B项目中A中没有匹配项目,或者A和B中项目相同.

更一般地,用于集合差异的算法取决于集合的表示.例如,如果将该集合表示为位向量,则上述将过于复杂且缓慢 - 您只需循环执行按位运算的向量.如果该集合表示为哈希表(如在tr1 unordered_set中),则上述错误,因为它需要有序输入.

如果你有自己的二进制树代码用于集合,一个很好的选择是将两个树转换为链表,处理列表,然后将结果列表转换为完美平衡的树.链表集差异非常简单,两次转换可重复用于其他类似操作.

编辑

关于复杂性 - 使用这些有序类似合并的算法是O(n),前提是您可以在O(n)中执行有序遍历.转换为列表并返回也是O(n),因为三个步骤中的每一个都是O(n) - 树到列表,设置差异和列表到树.

树到列基本上进行深度优先遍历,解析树的运行.这是进行迭代的一个技巧,将"堆栈"存储在部分处理的节点中 - 在您步入左子节点之前将左子指针更改为父指针.如果树可能很大且不平衡,这是一个好主意.

将列表转换为树基本上包括对假想树进行深度优先遍历(基于大小,从一开始就知道),将其构建为真实的.例如,如果一棵树有5个节点,你可以说根将是节点3.你试图构建一个双节点左子树,然后从列表中获取该根的下一个项,然后递归建立一个 - 节点右子树.

列表到树的转换不需要迭代实现 - 递归很好,因为结果总是完美平衡.如果你无法处理log n递归深度,你几乎肯定无法处理整个树.