ListMap：刪除最小值的m個最小元素

Question

我必須做一個函數，輸入一個整數m，並刪除最小值的map的m元素。 我的主要問題是O（nlogn）的複雜性。 （n是地圖的大小）

這是我的解決方案：

if (Map.isEmpty()) 
    return; 
if (Map.size()<m){ //remove all keys 
     Iterator<K> it=Map.keys().iterator(); //collection of all keys 
     while (it.hasNext()) 
      Map.remove(it.next()); 
} 
else{ 
for (int i=0; i<m; i++){ 
    key=Map.findKeyMin() //complexity:O(n) 
    Map.remove(K); 
} 

Answer 1

你可以在O（n）的時間做到這一點。看看http://en.wikipedia.org/wiki/Selection_algorithm。基本上，你可以找到第m個元素並刪除小於或等於第m個元素的所有內容。

Answer 2

您的解決方案具有複雜度爲O（N * M），這是最理想的。在c++<algorithm>標題中有一個函數，名爲nth_element該函數是線性的，將會將集合中的最小元素與其他元素分開。該函數是通過修改qsort算法實現的，我相信這是您在這裏需要的。