第k小 题解
题目描述
给定一个长度为 的数组，初始元素为 。需要支持 次操作：
添加操作：1 x - 向数组添加元素
查询操作：2 - 查询当前数组的第 小元素
如果数组元素少于 个，输出 -1。
示例： 数组 [1,2,2,3,4,6] 的第3小元素是 2。
核心结论
答案： 使用
展开全文
类似于求中位数，求中位数是将前一半小的数放入大顶堆，而本题可以前k小的数放入大顶堆中，因此维护大小始终为k的大顶堆即可。
对于准备插入的数
如果size小于k就直接插入
大于等于堆顶就跳过
小于堆顶就踢出当前堆顶，插入
import java.io.*;
import java.ut
展开全文
//建立两个堆，一个大根堆，一个小根堆。从K处劈开
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
const int maxn&nb
展开全文
Ciallo～(∠・ω< )⌒☆,大家好，本蒻蒟的第一篇题解，不喜勿喷。首先这题可以先用设置两个优先队列，一个大根堆p，一个设置成小根堆q，先用大根堆p存储输入数据，再用小根堆q维护前K个数据，当小于等于q的堆顶元素时入队，大于时入怕，最后输出去q的堆顶元素即可。
#include<io
展开全文
最开始我的想法是把所有数据都保存在优先队列里，然后每当弹出时就用其他容器接住，然后再放回优先队列中，结果果不其然超时了。
于是看了题解，觉得有道理，可以用大根堆（less）来保存，先将所有数据保存在堆中，如果堆的大小大于k，那么也就是说后面的数据压根不可能成为答案，所以就出队。然后接着进行选择，如果
展开全文
优先队列，保证元素数量 。
#include <iostream>
#include <queue>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
展开全文
链接：https://ac.nowcoder.com/acm/problem/214362
来源：牛客网
题目描述
有一个长度为n的数组，值为 a[i], 牛牛想找到数组中第 k 小的数。比如 1 2 2 3 4 6 中，第 3 小的数就是2.
展开全文
双堆解法
类似于双堆求中位数
把前k小的数放进大根堆，大根堆的堆顶恰好就是第k小的数
剩下的数放进小根堆里
如果要插入一个x
如果x比大根堆堆顶大，就扔进小根堆不管它了
如果x比大根堆堆顶小，取出大根堆堆顶，把堆顶那个数放进小根堆，再把x放入大根堆
查找的时候，大根堆如果size是k，那么大根堆堆顶
展开全文
使用优先队列维护数组中前 小的数。
对于初始化与操作 ，对于每个元素首先 进堆，此时如果 则不用处理，否则当前 ，进行一次 操作一定会弹出当前第 小的元素，可保证堆顶元素仍为第 小。
对于操作 ,如果 代表数组内还没有 个数，输出 ，否则输出堆顶元素即可。
#include <
展开全文
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fc freopen("in.in", "r", stdin), freopen("o
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
