题解 | #寻找第K大#

import java.util.*;
/**
 快速排序思路,每次找一个值,确定这个值在最终排序数组中的最终位置!
 **/
public class Solution {
    // 直接排序也能达到时间复杂度O(nlogn)
    public int findKth(int[] arr, int n, int k) {
        return quickSort(arr,0,n-1,k);
    }

    // 二分查找!
    private int quickSort(int[] arr,int from,int to,int k){
        int index = partion(arr,from,to);
        if(k == index - from + 1) return arr[index];
        if(index - from + 1 > k) // 在左边!
            return quickSort(arr,from,index - 1,k);
        // 在右边!
        return quickSort(arr,index + 1,to,k-(index - from + 1));
    }



    // 返回这个数在有序区间的位置!
    private int partion(int[] arr,int from,int to){
        int lt = from,rt = to;
        int pivot = arr[from];
        while(lt < rt){
            while(lt < rt && arr[rt] <= pivot){
                rt--;
            }
            arr[lt] = arr[rt];

            while(lt < rt && arr[lt] >= pivot){
                lt++;
            }
            arr[rt] = arr[lt];
        }
        // lt == rt
        arr[lt] = pivot;
        return lt;
    }
}