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