当前位置：首页 > article >正文

第k小（经典Top k问题）

article 2025/1/19 10:46:26

题目描述：

有一个长度为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;
}