algorithm - ListMap：删除m个最小的元素值最小的

Question

我必须做一个函数，输入一个整数 m，并删除地图中具有最小值的 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++中有一个函数，称为此函数是线性的，它将集合中的最小元素与其他元素分开。该功能是使用 qsort 算法的修改实现的，我相信这就是您需要的。<algorithm>nth_elementn