返回数据流中，第k大的数

问题：

数组int arr[]={3,4,7,1,5,6,9,2,8,0,...}数据流中，如何得到第k大的数？

分析：

比如说返回第2大的数，{3,4}中第二大的数就是3，{3,4,7}中第二大的数就是4..

方法一：

最简单直接的方法就是每新增一个数，将数组排序，之后取其中第二大的元素，时间复杂度为 N.KlogK，效率相对比较低。

方法二：

利用小顶堆特性（minHeap），使得堆的个数等于K。
每次进来一个数都与堆顶进行比较，小于等于堆顶元素就不用管了，没得比，第K大的数就是堆顶元素，大于堆顶元素，那就踢掉堆顶元素，加入新的元素进行堆排，得到新的堆顶元素就是第K大的元素。时间复杂度为N.logK。相比方法一要优化一些，贴一下代码：

/**
 * 返回数据流中，第k大的数。
 */
public class KthLargest {
    public static void main(String[] args){
        int arr[]={3,4,7,1,5,6,9,2,8,0};
        new KthLargest(3, arr);
    }
    final PriorityQueue<Integer> q;
    final int k;
    public KthLargest(int k,int[] arr) {
        this.k = k;
        this.q = new PriorityQueue<>(k);
        for (int x : arr)
            System.out.println(x+"进来，"+"第"+k+"大的数是"+add(x));
    }
    public int add(int x){
        if (q.size() < k) {
            q.offer(x);
        } else if (q.peek() < x) {
            q.poll();
            q.offer(x);
        }
        return q.peek();//第k大的数就是它了
    }
}

运行结果：

3进来，第3大的数是3
4进来，第3大的数是3
7进来，第3大的数是3
1进来，第3大的数是3
5进来，第3大的数是4
6进来，第3大的数是5
9进来，第3大的数是6
2进来，第3大的数是6
8进来，第3大的数是7
0进来，第3大的数是7