LeetCode题解：寻找第K大数

题目描述

有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
要求：时间复杂度 O(nlogn)，空间复杂度 O(1)

示例

• 示例1
  输入：[1,3,5,2,2],5,3
  输出：2
• 示例2
  输入：[10,10,9,9,8,7,5,6,4,3,4,2],12,3
  输出：9
  说明：去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9 。

方法思路

典型的快速排序
1、进行一次快排，大元素在左，小元素在右，得到的中轴p点；
2、如果 p - low + 1 = k ，那么p点就是第K大。
3、如果 p - low + 1 > k，则第k大的元素在左半段，更新high = p - 1，执行step 1。
4、如果 p - low + 1 < k，则第k大的元素在右半段，更新low = p + 1, 且 k = k - (p - low + 1)，排除掉前面部分更大的元素，再执行step 1。

import java.util.*;

public class Solution {
    //常规的快排划分，但是这次是大数在左
    public int partion(int[] a,int low,int high){
        int temp = a[low];
        while(low<high){
            //小于标杆的在右
            while(low<high && a[high]<=temp){
                high--;
            }
            if(low==high){
                break;
            }else{
                a[low] = a[high];
            }
            //大于标杆的在左
            while(low<high && a[low]>=temp){
                low++;
            }
            if(low==high){
                break;
            }else{
                a[high] = a[low];
            }
        }
        a[low] = temp;
        return low;
    }
    public int quickSort(int[] a,int low,int high,int K){
        //先进行一轮划分，p下标左边的都比它大，下标右边都比它小
        int p  = partion(a,low,high);
        //若p刚好是第K个点，则找到
        if(K == p-low+1){
            return a[p];
        }else if(p-low+1>K){
            //从头到p超过k个数组，则目标在左边
           return quickSort(a,low,p-1,K); 
        }else{
            //否则，在右边，递归右边，但是需要减去左边最大的数字的数量
            return quickSort(a,p+1,high,K-(p-low+1));
        }
    }
    public int findKth(int[] a, int n, int K) {
        // write code here
        return quickSort(a,0,n-1,K);
    }
    
}