m0_59314555 2021-06-15 10:34 采纳率: 0%
浏览 208

求最大的前K项,使用的是大顶堆还是小顶堆?是不是两种堆都适用, 为什么?

求最大的前K项,使用的是大顶堆还是小顶堆?是不是两种堆都适用,

为什么?

 

  • 写回答

3条回答 默认 最新

  • 关注

    用大顶堆

    大顶堆:每个结点的值都大于等于其左右孩子结点的值

    小顶堆:每个结点的值都小于等于其左右孩子结点的值

    class Solution {
    public:
        vector<int> getLeastNumbers(vector<int>& arr, int k) {
            vector<int>vec(k, 0);
            if (k == 0) return vec; // 排除 0 的情况
            priority_queue<int>Q;
            for (int i = 0; i < k; ++i) Q.push(arr[i]);
            for (int i = k; i < (int)arr.size(); ++i) {
                if (Q.top() > arr[i]) {
                    Q.pop();
                    Q.push(arr[i]);
                }
            }
            for (int i = 0; i < k; ++i) {
                vec[i] = Q.top();
                Q.pop();
            }
            return vec;
        }
    };
    
    
    评论

报告相同问题?

悬赏问题

  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能
  • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
  • ¥50 NT4.0系统 STOP:0X0000007B
  • ¥15 想问一下stata17中这段代码哪里有问题呀
  • ¥15 flink cdc无法实时同步mysql数据
  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决