假設您想要實現一個模板化函數，該函數將兩個迭代器放入一個容器中，並描述一個整數，該整數描述「容器中的元素是否在容器中的數量少於<整數>次，然後從容器中彈出它。「這樣的聲明可能是：從O（n）時間的容器中刪除<number>
template <class theIter>
theIter pop_um(theIter start, theIter end, int fewerThan);
是否有可能在O（n）時間寫這樣的函數？常用什麼程序來執行這樣的任務？
存儲桶/基數對數據（從開始到結束迭代器）進行排序，以線性時間開始。然後以線性時間掃描新的排序列表，記錄元素何時更改並易於彈出。線性時間。 O（2n）= O（n）。儘管取決於你的排序方式，但需要大量內存。
不鬥分類有時間複雜度O（n^2）？ – 2013-02-20 01:51:39
另請注意，這不必包含整數。例如，它可以包含單詞。 – 2013-02-20 01:59:09
基數排序也可以在線性時間內處理單詞，只是速度不如線性時間快。並且桶排序最壞的情況是O（n^2），而基數排序是線性的。他們在我心中都非常相似，這就是爲什麼我一起提到他們。我仍然很確定我的解決方案可以在線性時間內工作，並堅持下去，直到其他人提出更好的解決方案。 – 2013-02-20 16:43:33
任何代碼寫入試圖做到這一點呢？沒有冒犯，但這看起來像是一個功課問題的剪切和粘貼。 – 2013-02-20 00:38:38
我從一本教科書中得到了問題（推薦），所以它不是特別的功課。我很困惑如何在O（n）中完成刪除操作;也就是說，我們如何快速確定哪些元素出現的次數少於？ – 2013-02-20 00:42:17
聽起來像你剛纔掃描你的容器從「開始」到「結束」檢查每個元素對「少量」變種。如果需要彈出該值，則彈出該值。請記住，一旦你彈出它，你的迭代器可能是無效的。由於你的「容器」似乎只能保持一個單一的值，所以這是一個O（n）解決方案 - 一次通過列表的線性時間。如果每個容器都包含要檢查的對象，那麼它將是O（n * n）速度並且不符合您的標準。 – 2013-02-20 00:46:09