第k小 题解

题目描述

给定一个长度为 的数组，初始元素为 。需要支持 次操作：

1. 添加操作：1 x - 向数组添加元素
2. 查询操作：2 - 查询当前数组的第 小元素

如果数组元素少于 个，输出 -1。

示例： 数组 [1,2,2,3,4,6] 的第3小元素是 2。

核心结论

答案： 使用大根堆维护最大的 个元素，堆顶即为第 小元素。

关键思想： 第 小元素 = 所有元素中第 小的数 = 最大的 个元素中最小的那个。

标程实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, k, x, i;
    cin >> n >> m >> k;
    
    // 使用大根堆维护最大的k个元素
    priority_queue<int> q;
    
    // 初始化：将前n个元素加入堆
    for (i = 0; i < n; i++) {
        cin >> x;
        q.push(x);
        if (q.size() > k) q.pop();  // 保持堆大小为k
    }
    
    // 处理m次操作
    while (m--) {
        int op;
        cin >> op;
        
        if (op == 2) {  // 查询操作
            if (q.size() == k) {
                cout << q.top() << '\n';  // 堆顶就是第k小元素
            } else {
                cout << -1 << '\n';       // 元素不足k个
            }
        } else {        // 添加操作
            cin >> x;
            q.push(x);
            if (q.size() > k) q.pop();    // 保持堆大小为k
        }
    }
}

算法解释

核心思想

要找到第 小元素，我们可以维护最大的 个元素：

• 当元素总数 时，第 小元素就是最大的 个元素中最小的那个
• 当元素总数 时，不存在第 小元素

算法步骤

1. 初始化：将前 个元素加入大根堆，保持堆大小为
2. 添加操作：
   • 将新元素加入堆
   • 如果堆大小超过 ，弹出堆顶（最大的元素）
3. 查询操作：
   • 如果堆大小等于 ，堆顶就是第 小元素
   • 否则输出 -1

关键技巧

• 大根堆：priority_queue<int> 默认是大根堆
• 堆大小控制：始终保持堆中有最大的 个元素
• 堆顶性质：大根堆的堆顶是最大的 个元素中的最小值

复杂度分析

• 时间复杂度：
  • 初始化：
  • 每次操作：
• 空间复杂度：