首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >将元素排序到“回收箱”C++中

将元素排序到“回收箱”C++中
EN

Stack Overflow用户
提问于 2020-01-30 15:25:32
回答 1查看 310关注 0票数 0

你好,我一直在想,在c++中,将元素排序为“回收箱”最有效的方法是什么。

例如,我们可能有3个垃圾箱:

  • Bin A接受0-10的整数
  • Bin B接受5-20个整数。
  • Bin C接受25-30个整数。

我希望能够根据bin接受的范围将一个整数放入正确的bin中。如果int落入多个回收箱的范围内,则将其放入最不满的桶中。最后,我想知道整数是否适合于任何bin。

,什么是最有效的方法?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-01-30 15:39:45

那得看情况。

如果回收箱的数量很小,那么简单的线性搜索通常是非常有效的。特别是如果你考虑到程序员的时间。

如果整数集很小,而且回收箱不经常重叠,则可以在恒定时间内完成。我们创建一个由整数索引的向量,并以另一个(指向)回收箱的向量作为值。这样你就可以在恒定的时间内查找适用的垃圾箱列表。您仍然需要遍历适用的回收箱,以找出哪个是最不满的,因此,如果重叠桶的最大数量被一个常量限制,那么这只是固定的时间。

如果整数集很大,但回收箱本身相对较小,我们可以做类似的事情,但使用哈希表而不是向量。

如果我们不能做任何假设,那么区间树可能是最好的解决方案。但其最坏的行为仍然与垃圾箱的数量成线性关系,因为所有的垃圾箱都可能重叠,都需要检查以找出最不满的垃圾箱。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/59989275

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档