第K个最大的数
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1: 输入: [3,2,1,5,6,4], k = 2 输出: 5 示例 2: 输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4
提示： • 1 <= k <= nums.length <= 10^5 -104^ <= nums[i] <= 10^4
1.要求时间复杂度为O(n),有两种方法，一种使用优先队列，一种是基于快排的思想
2.这是我写的代码，用的优先队列，但是复杂度不是O(n),而是O(nlogn),那优先队列的时间复杂度是logn？看看源码
代码语言：javascript复制private final static int max= 10^5 1;
//优先队列PQ
//给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
//max 为 不合规input
public static int func(int[] nums,int k) {
if(nums==null || nums.length<k) {
return max;
}
int result = max;
PriorityQueue queue = new PriorityQueue<Integer>();
for(int i:nums) {
queue.add(i);
}
int length = queue.size();
System.out.println("size" length);
for(int n = 0;n<=length-k;n ) {
if(!queue.isEmpty()) {
result = (int) queue.poll();
}else {
result = max;
}
System.out.println("result:" result);
}
return result ;
}3.优先队列的add方法源码
1.PriorityQueue.add()
代码语言：javascript复制public boolean add(E e){
return offer(e)
}
public boolean offer(E e){
if(e == null)
throw new NullPointerException();
modCount ;
int i = size;
if(i >= queue.length)
//扩容 ，容量翻倍
grow(i 1);
size = i 1;
if(i == 0)
queue[0] = e;
else
siftUp(i,e);
return true;
}2.siftUp 新增
代码语言：javascript复制private void siftUp(int k,E x){
if(comparator != null)
siftUpUsingComparator(k,x);
else
siftUpComparable(k,x);
}3.siftUpComparable() 这里能看出来，果然复杂度是logn
代码语言：javascript复制@SuppressWarnings("unchecked")
private void siftUpComparable(int k,E x){
Comparable<? super E> key = (Comparable<? super E>) x;
while(k > 0){
int parent = (k-1)>>>1;
Object e = queue[parent];
if(key.compareTo((E) e)>=0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}4.那怎么才能把时间复杂度从O(nlogn)优化成O(n)呢
我们注意到，优先队列每次新增，都会有logn的开销，所以想要降低时间复杂度，就必须要降低开销的次数，减少add操作，把减少的部分尽量换成时间复杂度为O(1)的比较操作，这样假设有m次add，那么有（n-m）次比较，综合起来就是O(klogk） O(n-k）
题目中要求第K个最大的数，数组长度是N，所以定义堆的时候大小为K，然后用剩下的N-k个数和堆顶元素比较，最后堆顶即为结果：
（1）如果K>2/N,最好做（N-K）次add操作。第K个最大的数，就是第（N-K）个最小的数，因此用（N-K）大小的最大堆，堆顶就是结果。 1——————K——N （N-K）次add
（2）如果K<2/N,最好做K次add操作。用K大小的最小堆，堆顶就是结果。 1——K——————N K次add
代码语言：javascript复制public static int function(int[] nums,int k){
System.out.println("step into function");
int len = nums.length;
int top = 0;
int result = 0;
if(k <= len - k){
//最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k,(a,b) -> a-b);
for(int i = 0;i<k;i ){
minHeap.add(nums[i]);
printHeap(minHeap);
}
for(int i = k;i<len;i ){
top = minHeap.peek();
if(nums[i]>top){
minHeap.poll();
minHeap.add(nums[i]);
printHeap(minHeap);
}
}
result = minHeap.peek();
}else{
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(len-k 1,(a,b) -> b-a);
for(int i=0;i<len-k 1;i ){
maxHeap.add(nums[i]);
printHeap(maxHeap);
}
for(int i=len-k 1;i<len;i ){
top = maxHeap.peek();
if(nums[i]<top){
maxHeap.poll();
maxHeap.add(nums[i]);
}
}
result = maxHeap.peek();
}
return result;
}
