知识卡片

普通读书笔记卡 · 3725.b.1.v · 生成模型:未记录

对称差保留只在一边的成员

理解等级:中级

对称差A△B只保留恰好属于一边的成员,可写(A−B)∪(B−A)。两份差集天然互不重叠,因此构造这两份结果后,可以直接把成员地址接入最终结果节点,而无需再次通过通用并集逐项查重。

这个优化来自已证明的互斥关系,不能对任意两个集合都省略重复检查。在本章链表模型中,求两份差集仍要相互查找,所以省去最后查重未必改变总渐近等级,但减少了不必要工作;新结果的节点与借用数据清理责任仍要区分。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      两个集合的对称差由那些只在其中一个集合中出现过的成员组成。集合S1与S2的对称差记为S1∆S2。如何利用本章讲到的操作来实现求解集合的对称差呢?这个操作能否以更高效的方式实现? 答:按照集合的定义,S1∆S2=(S1−S2)⋃(S2−S1)。因此,可以通过调用两次set_difference以及一次

    参考来源

    - 位置:《算法精解:C语言描述》第7章《问与答》(spine1264;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1231.html;u117-ch07-023)。 - 结论依据:117对称差完整长问答、互不相交例与m+n次插入说明实读;未将3mn当精确运行时间,也未实现未给出的新函数。 - 原始内容:两个集合的对称差由那些只在其中一个集合中出现过的成员组成。集合S1与S2的对称差记为S1∆S2。如何利用本章讲到的操作来实现求解集合的对称差呢?这个操作能否以更高效的方式实现? 答:按照集合的定义,S1∆S2=(S1−S2)⋃(S2−S1)。因此,可以通过调用两次set_difference以及一次