将元素排序到“回收箱”C++中
将元素排序到“回收箱”C++中
提问于 2020-01-30 15:25:32
你好，我一直在想，在c++中，将元素排序为“回收箱”最有效的方法是什么。
例如，我们可能有3个垃圾箱：
- Bin A接受0-10的整数
- Bin B接受5-20个整数。
- Bin C接受25-30个整数。
我希望能够根据bin接受的范围将一个整数放入正确的bin中。如果int落入多个回收箱的范围内，则将其放入最不满的桶中。最后，我想知道整数是否适合于任何bin。
，什么是最有效的方法？
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-01-30 15:39:45
那得看情况。
如果回收箱的数量很小，那么简单的线性搜索通常是非常有效的。特别是如果你考虑到程序员的时间。
如果整数集很小，而且回收箱不经常重叠，则可以在恒定时间内完成。我们创建一个由整数索引的向量，并以另一个(指向)回收箱的向量作为值。这样你就可以在恒定的时间内查找适用的垃圾箱列表。您仍然需要遍历适用的回收箱，以找出哪个是最不满的，因此，如果重叠桶的最大数量被一个常量限制，那么这只是固定的时间。
如果整数集很大，但回收箱本身相对较小，我们可以做类似的事情，但使用哈希表而不是向量。
如果我们不能做任何假设，那么区间树可能是最好的解决方案。但其最坏的行为仍然与垃圾箱的数量成线性关系，因为所有的垃圾箱都可能重叠，都需要检查以找出最不满的垃圾箱。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/59989275
复制相关文章
相似问题
腾讯云开发者
