0

我必须做一个函数,输入一个整数 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);
}
4

2 回答 2

0

您可以在 O(n) 时间内完成。看看http://en.wikipedia.org/wiki/Selection_algorithm。本质上,您找到第 m 个元素并删除小于或等于第 m 个元素的所有内容。

于 2013-04-18T19:09:46.850 回答
0

您的解决方案具有次优的复杂度 O(n*m)。在标题c++中有一个函数,称为此函数是线性的,它将集合中的最小元素与其他元素分开。该功能是使用 qsort 算法的修改实现的,我相信这就是您需要的。<algorithm>nth_elementn

于 2013-04-18T10:32:31.517 回答