gpt4 book ai didi

c++ - 在 O(n) 时间内从容器中移除 个元素

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:08:53 26 4
gpt4 key购买 nike

假设您想实现一个模板化函数,该函数将两个迭代器带到一个容器和一个整数,该整数描述“如果容器中的元素在容器中出现的次数少于<整数>次,则将其从容器中弹出。”这样的声明可以是:

template <class theIter>
theIter pop_um(theIter start, theIter end, int fewerThan);

是否可以在 O(n) 时间内编写这样的函数?执行此类任务通常使用哪些程序?

最佳答案

桶/基数排序您的数据(从开始到结束迭代器)以线性时间开始。然后以线性时间扫描新的排序列表,跟踪元素何时更改并使其易于弹出。线性时间。 O(2n) = O(n)。根据您的排序方式,存储桶会占用大量 RAM。

关于c++ - 在 O(n) 时间内从容器中移除 <number> 个元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14970237/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com