29.最小的 k 个数

  • A+
所属分类:剑指offer

题目描述

输入n个整数,找出其中最小的 K 个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。

思路

如果用快排的话, 复杂度是O(nlogn), 但是这是全排列了, 没用上"最小的 K 个数"这个条件. 用上这个条件的话, 复杂度可以更低一点达到 O(nlogk).

思路就是用最大堆只保存最小的 k 个数, 堆顶是这 k 个数中最大的, 遍历数组, 如果遇到小于堆顶的, 删除堆顶数字, 让这个数进堆.

新的堆堆顶仍然是最小的 k 个数最大的, 因此我们取这个值复杂度是 O(1), 但是删除和插入操作的复杂度是 O(logk).

multiset是红黑树实现的, 用它实现最大堆.

代码

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(k < 1 || k > input.size())
            return vector<int>{};
        multiset<int, greater<int>> leastK;
        multiset<int, greater<int>>::iterator it;
        for(auto i = input.begin(); i != input.end(); i++){
            if(leastK.size() < k)
                leastK.insert(*i);
            else{
                it = leastK.begin();
                if(*i < *it){
                    leastK.erase(it);
                    leastK.insert(*i);
                }
            }
        }
        vector<int> res;
        it = leastK.begin();
        for(int i = 0; i < k;it++, i++){
            res.push_back(*it);
        }
        return res;
    }
};

29.最小的 k 个数

 

avatar

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: