c++ - 消除在 O(n) 时间内来自容器的元素

Question

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

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

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

Answer 1

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