第k小（经典Top k问题）

题目描述：

有一个长度为n的数组，值为 a[i], 牛牛想找到数组中第 k 小的数。比如 1 2 2 3 4  6 中，第 3 小的数就是2.

牛牛觉得这个游戏太简单了，想加一点难度，现在牛牛有 m 个操作，每个操作有两种类型。

1 x  1 代表操作一，给数组中加一个元素 x 。(0 ≤ x ≤ 1e9)

2     2 代表操作二，查询第 k 小的数。如果没有 k 个数就输出−1

输入描述:

第一行有三个整数，n m k,(1≤n,m,k≤2e5)

第二行包含 n 个整数 a[i] ( 0 ≤ a[i] ≤ 1e9)

接下来m行，每行代表一个操作。具体见题目描述

输出描述:

每次查询输出一个第 k 小的数。

示例1

输入

5 4 3 1 2 3 4 5 2 1 1 1 3 2

5 4 3
1 2 3 4 5
2
1 1
1 3
2

输出

3 2

3
2

解题思路： 

这是一道经典的 topk 问题，要求最小的第k个数或者最大的第k的数。通常我们会采用堆的形式来解决此类问题。如果我们要求最小的第k个数，那么我们就要建大根堆（从上到下逐渐减少）。将k个数据push到堆中，堆会按照由大到小的堆数据。一旦超过k个数据，就将堆顶出堆，这样就保证了堆顶是第k小（一次进一个，每次出最大）。同理可得，第k大也是同样的道理。该题的建堆时间复杂度为O（k），排序的时间复杂度为O（k logn）。

代码样例：

#include <iostream>
#include <queue>
using namespace std;

int n, m, k;
priority_queue<int> heap;
int op;

int main()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
{
int x; cin >> x;
heap.push(x);//默认大根堆
if (heap.size() > k)
{
heap.pop();
}
}
while (m--)
{
cin >> op;
if (op == 1)
{
int x; cin >> x;
heap.push(x);
if (heap.size() > k)
{
heap.pop();
}
}
else
{
if (heap.size() >= k)
{
cout << heap.top() << endl;
}
else
{
cout << "-1" << endl;
}
}
}
return 0;
}

题目链接：

第 k 小https://ac.nowcoder.com/acm/problem/214362

原文地址：https://blog.csdn.net/2401_86449430/article/details/145231694

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！