求解第K大元素,第K小元素/前k大元素,前k小元素/中位数 (堆·二叉堆) poj1442/black box

92 阅读 0 评论 61 点赞

我是靠谱客的博主诚心月光，这篇文章主要介绍求解第K大元素,第K小元素/前k大元素,前k小元素/中位数 (堆·二叉堆) poj1442/black box，现在分享给大家，希望可以做个参考。

如何求解一个第k大元素or第k小元素问题呢?/前k大元素or前k小元素

- 这类问题通常会有两种情况,1· 有序数组求解第k大, 2·无序数组(前k小or前k大)

这类问题通常会有两种情况,1· 有序数组求解第k大, 2·无序数组(前k小or前k大)

通常对于第k大元素问题求解过程如下:
1·我们只需要用一个小顶堆
2·从数组中选择k个元素,加入堆中…按顺序加入即可,最小的元素一定是堆顶元素.
3·数组中剩下的元素依次与堆顶比较.(我们需维护小顶堆)
4·堆顶元素就是第k大堆元素

举例 1 2 3 4 5 求解第3大元素,我们只需要维护有3个元素堆小顶堆.我们直观的看第三大的就是3.
一开始将 1 2 3 加入堆中,1在堆顶.
第一轮 1 与 4 比较,大于堆顶元素则1出堆,4入堆此时堆顶为2
第二轮 2 与 5比较同上堆顶被调整为3
3便是我们需要的答案

第k小元素反之亦然,换成大顶堆

前k大元素 or 前k小元素

如果我们单一的用一个大顶堆或者一个小顶堆,难以解决这类问题
我们可以将这类问题抽象成求一个数组里的中位数问题
假设给一个数组在此借用POJ1442 的Black Box 题目
在这里插入图片描述

大概解释一下,输入了n个数,m次询问.m次询问就是让我们求前m个元素中,第m小的元素

如果只用一个堆,是没有办法做解决的

所以我们需要使用二叉堆(对顶堆)

所有小堆元素 > 大堆元素,即可在大堆的堆顶找到第m小的元素

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream> 
using namespace std;
#include <set>
#define MAX 30000
int val[MAX+5] ={0};
typedef pair <int ,int> PII;
set<PII> s1,s2;
int main() {
    int n;
    int m;
    cin >> n>> m;
    for(int i = 1; i <= n; i++){
        cin >> val[i];
    }
    for(int i = 1, j = 0; i <= m; i++) {
        int k;
        cin >> k;
        while ( j < k ) {
            ++j;
            if(s1.size() == 0 || -s1.begin()->first > val[j]){ //
                s1.insert(PII(-val[j],j));
            }else {
                s2.insert(PII(val[j],j));
            }
        }
        while (s1.size() > i) {
            s2.insert(PII(-s1.begin()->first , s1.begin()->second));
            s1.erase(s1.begin());
        }
        while (s1.size() < i) {
            s1.insert(PII(-s2.begin()->first , s2.begin()->second));
            s2.erase(s2.begin());
        }
        cout << -(s1.begin()->first) << endl;
    }
    return 0;
}