我试图在 O(n) 时间内解决一个问题，给定两个前向迭代器到一个容器的前面和一个容器的后面，我想删除容器中至少不出现的所有元素 <这个次数 > 次。例如，给定一个字符串向量，例如 ("john", "hello", "one", "yes", "hello", "one")，我想删除所有出现少于 2 次的元素，我的最终向量将只包含 ("hello", "one")。
我在想，如果我可以在 O(n) 时间内进行一般排序，我可以完成这个结果（在 O(n) 时间内），但我很难用字符串、整数、字符或其他任何可能被使用（一般）。我是否正确地考虑了这一点，还是有更简单的方法来解决问题？
是的，您实际上不是在排序而是删除元素。
1）。将每个单词存储到一个哈希集中。2）。查找并仅在不在哈希集中时添加。
简短的回答：没有。基于比较的排序需要O(n log n)时间。（这可以正式证明。）如果您对输入有所了解（例如，输入在已知范围内随机均匀分布），那么您可以及时使用众所周知的算法，例如桶排序或基数排序O(n)。与@Mooing Duck 不同，没有O(1)及时排序（这应该很明显——对于任何排序算法，您必须至少访问每个元素一次）。
但是，正如其他几位海报所指出的那样，您的问题不需要排序算法......
无需排序
1) 填充std::unordered_map<string,vector<int>> indexOfStrings;- O(N)
2) 对于每个string,vector size() < 2删除元素 - O(删除次数) <= O(N)
indexOfStrings- 存储字符串每次出现的索引。这允许从向量中快速删除而无需搜索。
你不需要排序，你只需要一个unordered_map：
unordered_map<string, int> counter;
vector<string> newvec;
for(string &s : v) {
if((++counter[s]) == 2) {
newvec.push_back(s);
}
}
请注意，这是 C++11 代码。（感谢@jogojapan 的代码改进建议）。