第 K 大的数

一 问题描述

小明和小宝正在玩数字游戏，游戏有 n 轮，小明在每轮中都可以写一个数，或者问小宝第 k 大的数是什么。游戏格式为：I c，表示小明写下一个数 c。Q，表示小明问第 k 大的数。请对小明的每个询问都给出第 k 大的数。

二 输入和输出 

1 输入

输入包含多个测试用例。每个测试用例的第 1 行都包含两个正整数n、k，表示 n 轮游戏和第 k 大的数。然后是 n 行，格式为 I c 或 Q。

2 输出

对每个询问 Q，都单行输出第 k 大的数。

三 输入和输出样例

1 输入样例

8 3

I 1

I 2

I 3

Q

I 5

Q

I 4

Q

2 输出样例

1

2

3

四 算法设计

1 使用优先队列（最小值优先）存储最大的 k 个数。

2 插入。若队中的元素小于 k，则直接入队；若当前输入元素大于队头，则队头出队，当前元素入队。

3 查询。队头（堆顶）就是第 k 大的数，输出即可。

五 图解

1 插入

I 1：元数个数小于 3，直接入队。I 2：元数个数小于 3，直接入队。I 3：元数个数小于 3，直接入队。

2 查询

查询第 3 大的数，队头 1 为第 3 大的数。数字 3 是第  大。

3 插入

I 5：元素个数不小于3，,5 比队头大，则队头出队，5 入队。

4 查询

查询第 3 大的数。对头 2 为第 3 大的数。

5 插入

I 4：元素个数不小于 3，4 比队头大，则队头出队，4 入队。

6 查询

查询第 3 大的数，队头 3 为第 3 大的数。

六 代码

package com.platform.modules.alg.alglib.hdu4006;
 
import java.util.PriorityQueue;
 
public class Hdu4006 {
    public String output = "";
 
    public String cal(String input) {
        int i, n, k, num;
        char c;
        String[] line = input.split("\n");
        String[] words = line[0].split(" ");
        n = Integer.parseInt(words[0]);
        k = Integer.parseInt(words[1]);
 
        PriorityQueue q = new PriorityQueue<>(); // 默认为小顶堆
 
        for (i = 1; i <= n; i++) {
            String[] command = line[i].split(" ");
            c = command[0].charAt(0);
            if (c == 'I') {
                num = Integer.parseInt(command[1]);
                if (q.size() < k) // 堆中元素个数小于 k
                    q.add(num);
                else if (q.peek() < num) { // 当堆顶小于输入元素时
                    q.poll();
                    q.add(num); // 堆顶出队，元素入队
                }
            } else //堆中永远保存最大的k个元素
                output += q.peek() + "\n";//堆顶即为第k大元素
        }
        return output;
    }
}

七 测试