当前位置:主页   - 电脑 - 程序设计 - C/C++
[算法]找出m个数中最小的n个数
来源:网络   作者:   更新时间:2011-11-07
收藏此页】    【字号    】    【打印】    【关闭

  这个问题属于常见问题了,我的办法是采用堆。

  截取STL中的partial_sort算法的实现:

template <class RandomAccessIterator, class T, class Compare>
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
                    RandomAccessIterator last, T*, Compare comp) {
  make_heap(first, middle, comp);
  for (RandomAccessIterator i = middle; i < last; ++i)
    if (comp(*i, *first))
      __pop_heap(first, middle, i, T(*i), comp, distance_type(first));
  sort_heap(first, middle, comp);
}

  上面这个函数是对一个序列进行部分排序,排序之后,在first,middle之间的元素有序。

  它的做法首先将原始的first,middle中的数据生成一个堆,然后遍历之后的数据,如果比前面的元素中最大的元素大,就把最小的元素删除插入这个新的元素,这个过程是lg(middle - first),最后进行堆排序。

  不是每个元素都需要重新调整堆,所以最坏的情况时间复杂度是n * lg(middle - first)。

  类似的,可以根据这个算法并且使用堆算法解决这个问题,如上所言,最坏的时间复杂度是n * lg(m),其中n是元素总量,m是待查找的最大的m个数。

  根据我上面的这个想法, 还有我原来写过的堆算法,给出解决这个问题的代码,由于我原来写的堆算法是大项堆(max-heap),也就是堆中最大的元素在根部,所以这里面求出来的是数中最小的10个数,如果要求最大的10个数,要讲这个堆改成小项堆,其实也就是改变堆中父子之间的大小关系罢了,其他的地方不变。

其它资源
来源声明

版权与免责声明
1、本站所发布的文章仅供技术交流参考,本站不主张将其做为决策的依据,浏览者可自愿选择采信与否,本站不对因采信这些信息所产生的任何问题负责。
2、本站部分文章来源于网络,其版权为原权利人所有。由于来源之故,有的文章未能获得作者姓名,署“未知”或“佚名”。对于这些文章,有知悉作者姓名的请告知本站,以便及时署名。如果作者要求删除,我们将予以删除。除此之外本站不再承担其它责任。
3、本站部分文章来源于本站原创,本站拥有所有权利。
4、如对本站发布的信息有异议,请联系我们,经本站确认后,将在三个工作日内做出修改或删除处理。
请参阅权责声明