整数数组中寻找第K大元素

算法思想

使用最大堆结构，最大堆的顶部总是最大元素。因此我们只需要构建一个最大堆，然后循环取K次堆顶就可以拿到目标元素。

堆是什么，怎么使用堆，这里不做讨论。

算法复杂度分析

• 构建堆：O(N)
• 取出K个元素，K常数，算法复杂度O(N)

上代码

import java.util.*;

public class Finder {
    PriorityQueue<Integer> maxHeap;

    public int findKth(int[] a, int n, int K) {
        // write code here
        createHeap(a, n);
        int val = 0;
        for(int i=0; i<K; i++){
            val = maxHeap.poll();
        }
        return val;
    }

    public void createHeap(int[] a, int n){
        maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return - Integer.compare(o1, o2);
            }
        });

        // add to the max heap
        for(int i=0; i<n; i++){
            maxHeap.offer(a[i]);
        }
    }
}

优化

取出K个元素，在K<1/2n时候，最大堆适用。如果K大于1/2*n, 用最小堆更划算。取元素次数可以保证小于1/2n

这个优化没啥难度，我就不写了