题解 | #寻找第K大#

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        if (a == null || n == 0 || K < 1 || K > n){
            return -1;
        }
        return partition(a, 0, n - 1, n - K);
    }
     private int partition(int[] a, int start, int end, int K) {
        if (start >= end) {
            return a[K];
        }

        int left = start, right = end;
        int pivot = a[(start + end) / 2];

        while (left <= right) {
            while (left <= right && a[left] < pivot) {
                left++;
            }
            while (left <= right && a[right] > pivot) {
                right--;
            }
            if (left <= right) {
                swap(a, left, right);
                left++;
                right--;
            }
        }

        if (K <= right) {
            return partition(a, start, right, K);
        }
        if (K >= left) {
            return partition(a, left, end, K);
        }
        return a[K];
    }    

    private void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}