题解 | #寻找第K大#

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int k) {
        // write code here
        return findKth(a, 0, n - 1, n - k + 1);
    }

    public int findKth(int[] a, int start, int end, int k){
        if(start >= end) return a[start];

        int left = start - 1, right = end + 1, mid = a[left + (right - left)/2];
        while(left < right){
            do left++; while(mid > a[left]);
            do right--; while(mid < a[right]);

            if(left < right){swap(a, left, right);}
            else break;
        }
        if(right >= k-1){ return findKth(a,start,right,k);}//因为第k大对应下标为k-1}
        else {return findKth(a, right + 1, end, k);}
    }

    public static void swap(int[] q, int p1, int p2){
        int temp = q[p1];
        q[p1] = q[p2];
        q[p2] = temp;
    }
}