首页 > 其他 > 详细

item30,最小的k个数

时间:2016-06-23 22:08:54      阅读:227      评论:0      收藏:0      [点我收藏+]

剑指offer给出两类方法:

1,借助快排的思想,需要修改输入数组的元素,时间复杂度O(n)

2,借助STL中set或者multiset,因为它们的底层数据结构是红黑树实现的,插入数据时间复杂度为O(logk),所以总的时间复杂度为O(nlogn);

==========

方法2的代码如下:

typedef std::multiset<int,greater<int> > intset;
    typedef std::multiset<int,greater<int> >::iterator iteratorset;

    void getLeastNumber(vector<int> nums,intset& leastNumber,int k){
        int length = nums.size();

        leastNumber.clear();
        if(length <k) return;
        for(auto i:nums){
            if(leastNumber.size()<(unsigned int)k){
                leastNumber.insert(i);
            }else{
                iteratorset itset = leastNumber.begin();
                if(i<*itset){
                    leastNumber.insert(i);
                    leastNumber.erase(leastNumber.begin());
                }
            }///if-else
        }///for
    }///end-function

 

item30,最小的k个数

原文:http://www.cnblogs.com/li-daphne/p/5612306.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!