【每日一道算法题】寻找第K大的数

有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。

• 示例1

输入
[1,3,5,2,2],5,3
输出
2

题解：
可以使用快排+二分法的思想
快排在排序时，会把数组分成两部分，一部分小于一个值，另一部分大于这个值。
1.将数组用快排从大到小排序，取key值为数组的第一个数a[start],
 那么经过一轮调整之后，数组左边的所有值大于或等于key，
 数组右边的所有值都小于或等于key。
2.假设此时key是数组第i个数
 如果i正好等于K，那么key就是第K大值
 如果i大于K，那么说明第K大值在数组左边，则继续在左边查找
 如果i小于K，那么说明第K大值在数组的右边，继续在右边查找
 每一轮排序都重复上述步骤，直到找到第K大值。

快排+二分的思想

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
       return quickSort(a,0,n-1,K);
    }
    
    public int quickSort(int[] a, int start,int end, int K){
        int p=partition(a,start,end);
        if(p==K-1){
            return a[K-1];
        }else if(p>K-1){
            quickSort(a,start,p-1,K);
        }else{
            quickSort(a,p+1,end,K);
        }
        return a[K-1];
        
    }
    //找快排的分割点
    public int partition(int[] arr,int start,int end){
        int key=arr[start];
        while(start<end){
            while(start<end&&arr[end]<=key){
                end--;
            }
            swap(arr,start,end);
            while(start<end&&arr[start]>=key){
                start++;
            }
            swap(arr,start,end);
        }
        return start;
        
    }
    public void swap(int[] arr,int left,int right){
        int tem=arr[left];
        arr[left]=arr[right];
        arr[right]=tem;
    }
}