题解 | #最小的K个数#

最小的K个数

http://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf

我看到很多人都是使用的快速排序,这里分享一个使用最大堆的方式:

运行时间:3ms
占用内存:512KB

class Solution {
public:
    // miniK 使用最大堆
    void max_heapfiy(vector<int>& input, int begin, int end) {
        int    l       = begin * 2 + 1;
        int    r       = begin * 2 + 2;
        size_t largest = begin;
        if(l < end && input[l] > input[largest]) largest = l;
        if(r < end && input[r] > input[largest]) largest = r;
        if(largest != begin) {
            swap(input[begin], input[largest]);
            max_heapfiy(input, largest, end);
        }
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        // 构建堆
        for(int i = k / 2; i >= 0; --i) max_heapfiy(input, i, k);
        for(int i = k; i < input.size(); ++i) {
            if(input[i] < input[0]) {
                swap(input[0], input[i]);
                max_heapfiy(input, 0, k);
            }
        }
        return {input.begin(), input.begin() + k};
    }
};

这里唯一需要特别注意的是第十八行一定要是 int i = k 因为如果更小的话会导致堆顶与堆底元素发生交换,这时因为顶点的左右孩子没有变化,因此不会触发维护算法。这时就出错了。

比较遗憾的是看来测试集中没有大数据集,因此最大堆的好处体现不出来。反而比快速排序还要慢:

全部评论

相关推荐

04-25 18:13
五邑大学 Java
后来123321:大二两段实习太厉害了,我现在大二连面试都没有
点赞 评论 收藏
分享
06-06 03:40
已编辑
电子科技大学 Java
在秋招的小白菜很想养修勾:一眼 苍穹外卖+谷粒商城,项目换一换吧,可以找一些付费知识星球博主带带,避免烂大街。多投投大厂,背背八股,你这学历乱杀了,等实习经验到位,到时候大厂闭眼选
投递美团等公司7个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务