hihoCoder 1133 二分·二分查找之k小数(TOP K算法)

时间:2022-03-23 19:11:31

#1133 : 二分·二分查找之k小数

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

在上一回里我们知道Nettle在玩《艦これ》,Nettle的镇守府有很多船位,但船位再多也是有限的。Nettle通过捞船又出了一艘稀有的船,但是已有的N(1≤N≤1,000,000)个船位都已经有船了。所以Nettle不得不把其中一艘船拆掉来让位给新的船。Nettle思考了很久,决定随机选择一个k,然后拆掉稀有度第k小的船。 已知每一艘船都有自己的稀有度,Nettle现在把所有船的稀有度值告诉你,希望你能帮他找出目标船。

提示:非有序数组的二分查找之二

输入

第1行:2个整数N,k。N表示数组长度,
第2行:N个整数,表示a[1..N],保证不会出现重复的数,1≤a[i]≤2,000,000,000。

输出

第1行:一个整数t,表示t在数组中是第k小的数,若K不在数组中,输出-1。

样例输入
10 4
1732 4176 2602 6176 1303 6207 3125 1 1011 6600
样例输出
1732

题目链接:hihoCoder 1133

题目求的是第K小,即从小到大排序后正着数第K个数

例子:1 3 5 三个数中第3大是1,第3小是5,因此第K小用最大堆,第K大用最小堆,这个算法以前看了很久,由于堆不会写就完全看不懂,这次回来把它实现了一下,这份代码支持有重复出现的数的情况。

用堆求TOP K问题的简单步骤(堆的根记为Root):

1、将无序数据的前K个读入并插入空堆中。

2、继续从K+1个数据开始读入,若某个数据的关键字逻辑上比Root要小,则把Root用这个数据替换,一般情况下直接赋值给Root,然后向下调整堆,为什么?若这个数据比Root要小,则说明整个数组从小到大排序后这个数据的位置肯定在替换Root的前面,因此替换前的Root在读入这个数据后一定会被挤出前K个数之外,因此要替换掉

3、这样处理完N个数后所求的第K大/小就是最后留下的堆的根(代码中储存堆用顺序表且有效下标从1开始)

代码:

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 1000010;
class Maxm_Heap
{
private:
int A[N];
int sz;
public:
void init()
{
sz = 0;
}
void up(const int &cur)
{
int fa = cur >> 1;
if (fa > 0 && A[cur] > A[fa])
{
swap(A[cur], A[fa]);
up(fa);
}
}
void down(const int &cur)
{
int lson = cur << 1;
int rson = lson | 1;
if (lson > sz)
return ;
int son;
if (rson > sz)
son = lson;
else
son = A[lson] > A[rson] ? lson : rson;
if (A[son] > A[cur])
{
swap(A[son], A[cur]);
down(son);
}
}
void push(const int &val)
{
A[++sz] = val;
up(sz);
}
void pop()
{
swap(A[1], A[sz]);
--sz;
down(1);
}
int top()
{
return A[1];
}
void alt_top(const int &val)
{
A[1] = val;
}
};
Maxm_Heap heap; int main(void)
{
int n, k, i;
while (~scanf("%d%d", &n, &k))
{
heap.init();
int val;
for (i = 1; i <= k; ++i)
{
scanf("%d", &val);
heap.push(val);
}
for (i = k + 1; i <= n; ++i)
{
scanf("%d", &val);
if (val < heap.top())
{
heap.alt_top(val);
heap.down(1);
}
}
printf("%d\n", (k < 1 || k > n) ? -1 : heap.top());
}
return 0;
}