知识卡片
多重集合保留成员的重复次数
普通集合只关心成员存在与否,多重集合允许同一成员重复出现,适用于重复次数本身有意义的情况。删除某个值时,还需明确是移除一个出现还是全部出现;本段没有给统一接口约定。
117按本章链表表示比较:允许重复后,插入可省去查重,直接局部插节点为O(1)模型;按值移除仍需最坏O(n)搜索。这是该表示和接口条件下的分析,不是所有多重集合实现一律具有的复杂度。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
多重集合中的成员可以是重复的。在某些问题中,对于集合成员不允许重复的限制显得过于严格。对于这些问题,多重集合是一种替代传统集合的方法。
参考来源
- 位置:《算法精解:C语言描述》第7章《相关主题》(spine1265;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1232.html;u118-ch07-025)。
- 结论依据:118多重集合定义和117末组插入/移除比较全文实读;删除次数区别作为接口待明确的边界,不伪称书中已给实现。
- 原始内容:多重集合中的成员可以是重复的。在某些问题中,对于集合成员不允许重复的限制显得过于严格。对于这些问题,多重集合是一种替代传统集合的方法。