我有两个数组,比如说A和B,| A | = 8,| B | = 4。 我想计算设定差异AB。 我该怎么办? 请注意,任何一组中都没有重复的元素。
编辑:非常感谢大家提供无数优雅的解决方案。 由于我处于项目的原型设计阶段,现在我实施了Brian和Owen所说的最简单的解决方案。 但我很欣赏你们其他人在这里建议的数据结构的巧妙使用,即使我不是计算机科学家而是工程师,从未将数据结构作为课程进行研究。 看起来是时候我应该真正开始阅读我一直拖延了很长一段时间的CLRS :)再次感谢!
迭代A的每个元素,如果每个元素都不在B中,则将它们添加到新的集合C.
排序数组A和B.
结果将在C中
让a – A的第一个元素
让b – B的第一个元素
然后:
1)当a 2)而a> b:b = B的下一个元素
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并删除任何元素。
关键是为作业使用正确的数据结构。
对于较大的集合,我建议对数字进行排序并通过模拟https://www.cplusplus.com/reference/algorithm/set_difference/上的代码来迭代它们,这些代码将是O(N * logN),但是因为设置的大小如果这么小,Brian给出的解决方案看起来很好,即使它理论上在O(N ^ 2)处较慢。
需要了解更多c/c++开发分享如何计算C中两组之间的差异?,也可以关注C/ C++技术分享栏目---计算机技术网(www.ctvol.com)!
以上就是c/c++开发分享如何计算C中两组之间的差异?相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/979313.html