Leetcode-215. 数组中的第K个最大元素

215. 数组中的第K个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

解题思路
1.普通的排序，复杂度高-----快排、冒泡之类
2.改进的快排----我们通过比较中间元素的坐标（只排需要排的那一半）
3.小顶堆---这样每次比较大的元素会沉下去，大于k时，直接舍弃堆顶

后两者的代码如下

class Solution {
    //利用小顶堆的自动排序
    public int findKthLargest1(int[] nums, int k) {
        // 小顶堆，堆顶是最小元素
        PriorityQueue<Integer>  pq = new PriorityQueue<>();
        for(int num:nums){
            pq.offer(num);
            if(pq.size()>k){
                pq.poll();
            }
        }
        return pq.peek();
    }
    //利用快速排序：我们可以不排完
    public int findKthLargest(int[] nums, int k) {
        int[] results=qsort(nums,0,nums.length-1,k);
        return results[k-1];
    }
    //找第k大（从0开始的第k大）
    public int[] qsort(int[] array,int l,int r,int k){
        if(l<r){
            int q=part(array,l,r);
            if(q==k-1) return array;
            if(q<k-1) qsort(array,q+1,r,k);
            if(q>k-1) qsort(array,l,q-1,k);
        }
        return array;
    }

    public int part(int[] array,int l,int r){
        int num=array[l];
        int i=l;
        int j=r+1;
        while(true){
            while(array[++i]>num && i<r);//前半部分大，后序小
            while(array[--j]<num);
            if(i>=j) break;
            int temp=array[i];
            array[i]=array[j];
            array[j]=temp;
        }
        array[l]=array[j];
        array[j]=num;
        return j;
    }

}