题目描述

方法一：利用库函数直接排序

import java.util.*;
public class Finder {
    public int findKth(int[] a, int n, int K) {
        Arrays.sort(a);
        return a[n-K];  //n-K 为排序数组后数组中第K大的值的下标
    }
}

方法二：利用快排思想

import java.util.*;
public class Finder {
    public int findKth(int[] a, int n, int K) {
        int left = 0, right = n-1;
        //转换成目标值在数组中的索引
        int target = n-K;
        while(true){
            int index = partition(a,left,right);
            if(index == target)
                return a[index];
            //a[index] 为数组中第index大的值
            else if(index < target)
                left = index+1;
            else 
                right = index-1;
        }
    }
    public int partition(int[] a, int left, int right){
        //以该值为切片
        int pivot = a[left];
        int j = left;
        for(int i = left+1; i <= right; i++){
            //如果切片右边的数小于它，则把小的值放在切片的右邻
            if(a[i] < pivot){
                j++;
                swap(a,j,i);
            }
        }
        //此时上面循环算出来后区间[left+1,j]<pivot && [j+1,right]>pivot
        //下面我们交换left和j的值
        swap(a,left,j); //此时[left,j-1]<pivot && a[j]==pivot && [j+1,right]>pivot
        return j;  //此时因为pivot右边的值都比它大，左边的值都比它小，所以返回它的下标回到主程序判断是否为目标值的下标
    }
    public void swap(int[] a, int j, int i){
        int temp = a[j];
        a[j] = a[i];
        a[i] = temp;
    }
}

注意：本题必须随机初始化 pivot 元素，否则通过时间会很慢，因为测试用例中有极端测试用例。

为了应对极端测试用例，使得递归树加深，可以在循环一开始的时候，随机交换第 11 个元素与它后面的任意 11 个元素的位置；说明：最极端的是顺序数组与倒序数组，此时递归树画出来是链表，时间复杂度是 O(N^2)，根本达不到减治的效果。
优化后的代码

import java.util.*;
public class Finder {
    private static Random random = new Random(System.currentTimeMillis());
    public int findKth(int[] a, int n, int K) {
        int left = 0, right = n-1;
        //转换成目标值在数组中的索引
        int target = n-K;
        while(true){
            int index = partition(a,left,right);
            if(index == target)
                return a[index];
            //a[index] 为数组中第index大的值
            else if(index < target)
                left = index+1;
            else 
                right = index-1;
        }
    }
    public int partition(int[] a, int left, int right){
        //以一个随机下标对应的数组值为切片
        if(right>left){
            int randomIndex = left+1+random.nextInt(right-left);
            swap(a,left,randomIndex);
        }
        int pivot = a[left];
        int j = left;
        for(int i = left+1; i <= right; i++){
            //如果切片右边的数小于它，则把小的值放在切片的右邻
            if(a[i] < pivot){
                j++;
                swap(a,j,i);
            }
        }
        //此时上面循环算出来后区间[left+1,j]<pivot && [j+1,right]>pivot
        //下面我们交换left和j的值
        swap(a,left,j); //此时[left,j-1]<pivot && a[j]==pivot && [j+1,right]>pivot
        return j;  //此时因为pivot右边的值都比它大，左边的值都比它小，所以返回它的下标回到主程序判断是否为目标值的下标
    }
    public void swap(int[] a, int j, int i){
        int temp = a[j];
        a[j] = a[i];
        a[i] = temp;
    }
}

方法三：使用最小堆（最大堆）

思路：将全部的值放进一个最小堆中，此时poll出来n-K个值，然后堆顶的值就是我们想要的值了（最小堆）
poll出来K-1个值，然后堆顶就是我们想要的值了（最大堆）
最小堆的

import java.util.*;
public class Finder {
    public int findKth(int[] a, int n, int K) {
        //使用最小堆  默认是最小堆a-b
        PriorityQueue<Integer> minHeap = new  PriorityQueue<>(n,(a1,b)-> a1-b);
        for(int num:a){
            minHeap.add(num);
        }
        for(int i = 0; i < n-K; i++){
            minHeap.poll();
        }
        return minHeap.peek();
    }
}

最大堆的

import java.util.*;
public class Finder {
    public int findKth(int[] a, int n, int K) {
        // write code here
        //使用最小堆  默认是最小堆  现在是b-a1  所以为最大堆
        PriorityQueue<Integer> minHeap = new  PriorityQueue<>(n,(a1,b)-> b-a1);
        for(int num:a){
            minHeap.add(num);
        }
        for(int i = 0; i < K-1; i++){
            minHeap.poll();
        }
        return minHeap.peek();
    }
}