题解 | #寻找第K大#

import java.util.*;
public class Solution {
    public int findKth (int[] a, int n, int K) {
        //小顶堆
        PriorityQueue<Integer> q = new PriorityQueue<>((o1,o2)->o1.compareTo(o2));
        for(int i=0;i<K;++i){
            q.offer(a[i]);
        }
        for(int i=K;i<n;++i){
            if(q.peek()<a[i]){
                q.poll();
                q.offer(a[i]);
            }
        }
        int maxk=0;
        maxk = q.poll();
        return maxk;
    }
}

方法一：小顶堆

要求第k大元素，可以先求前k个最大元素，然后取最小，类比前一题的思想，用小顶堆可以求得前k个最大元素，然后堆顶就是第k大元素。

方法二：快排 + 二分查找

利用快速排序的思想，每次找到一个标杆元素，然后将小于它的值放右边，大于它的放左边，大的放左边原因是方便通过下标确定较大值的个数，然后分别递归左右两边，实现排序。在本题中，要求第k大，所以

• 若比标杆元素大的个数等于k-1个，那么此标杆为第k大；
• 若个数大于k-1个则说明第k大在左边，右边就不需要递归了；
• 相反，若比标杆大的不足k-1个，说明第k大在标杆的右边，递归左边即可，右边不用管了。

步骤：

1、使用随机数获取标杆元素，防止数据分布导致每次划分不能均衡。将标杆位置的值与本区间的最左端交换，确保标杆在最左端。

2、确定好标杆的值、和两个负责遍历的指针位置

3、进行一次快排，即从右往左找到一个比标杆大的值，从左往右找到比标杆小的值，二者交换，双指针移动，重复操作，直到左指针大于右指针，说明找不到满足条件的值，跳出循环。

4、将右指针 j 所指的值与标杆处的值交换。

5、根据上面的分析，通过大于标杆的个数判断是否找到第k大的值，否则向左或向右区间递归。

6、重复上述步骤直到找到第k大为止。

import java.util.*;
public class Solution {
    public static void swap(int[] arr,int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    Random r = new Random(); 
    public int partition(int[] a, int low, int high, int k){
        //随机快排划分，得到一个随机的标杆位置
        int x = Math.abs(r.nextInt()) % (high - low + 1) + low;
        swap(a,low,x);  //将标杆值放在本区间最左边
        int v = a[low]; //标杆值
        int i = low + 1; //从标杆的下一个位置开始
        int j = high; //
        while(true){
            //小于标杆的在右边
            while(j>low && a[j] < v){
                j--;
            }
            //大于标杆的在左边
            while(i<=high && a[i] > v){
                i++;
            }
            if(i>j){
                break;
            }
            swap(a,i,j);
		    i++;
            j--;
        }
        //交换标杆处与j位置的值
        swap(a,low,j);
        //左边为较大值，j从0开始,若左边的个数恰好为k-1个则标签值即为第k大
        if(j+1 == k){
            return a[j];
        }else if(j+1 < k){//左边个数不足k-1个
            return partition(a,j+1,high,k);
        }else{
            return partition(a,low,j-1,k);
        }
    }
    public int findKth (int[] a, int n, int K) {

        return partition(a,0,n-1,K);
    }
}