問(wèn)題：
數(shù)組int arr[]={3,4,7,1,5,6,9,2,8,0,...}數(shù)據(jù)流中辐啄，如何得到第k大的數(shù)采章？
分析：
比如說(shuō)返回第2大的數(shù)壶辜，{3,4}中第二大的數(shù)就是3，{3,4,7}中第二大的數(shù)就是4..
方法一：
最簡(jiǎn)單直接的方法就是每新增一個(gè)數(shù)砸民，將數(shù)組排序奋救，之后取其中第二大的元素，時(shí)間復(fù)雜度為 N.KlogK反惕，效率相對(duì)比較低。
方法二：
利用小頂堆特性（minHeap）姿染，使得堆的個(gè)數(shù)等于K背亥。
每次進(jìn)來(lái)一個(gè)數(shù)都與堆頂進(jìn)行比較悬赏，小于等于堆頂元素就不用管了，沒(méi)得比闽颇，第K大的數(shù)就是堆頂元素盾戴，大于堆頂元素，那就踢掉堆頂元素尖啡，加入新的元素進(jìn)行堆排，得到新的堆頂元素就是第K大的元素剩膘。時(shí)間復(fù)雜度為N.logK。相比方法一要優(yōu)化一些援雇，貼一下代碼：
/**
* 返回?cái)?shù)據(jù)流中矛渴，第k大的數(shù)惫搏。
*/
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+"進(jìn)來(lái)，"+"第"+k+"大的數(shù)是"+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大的數(shù)就是它了
}
}
運(yùn)行結(jié)果：
3進(jìn)來(lái)筐赔，第3大的數(shù)是3
4進(jìn)來(lái)，第3大的數(shù)是3
7進(jìn)來(lái)茴丰，第3大的數(shù)是3
1進(jìn)來(lái)达皿，第3大的數(shù)是3
5進(jìn)來(lái)贿肩，第3大的數(shù)是4
6進(jìn)來(lái)峦椰，第3大的數(shù)是5
9進(jìn)來(lái)汰规，第3大的數(shù)是6
2進(jìn)來(lái)，第3大的數(shù)是6
8進(jìn)來(lái)，第3大的數(shù)是7
0進(jìn)來(lái)状答，第3大的數(shù)是7
