题解 | #寻找第K大#

import java.util.ArrayList;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        // 思路：快排
        if (0 == n) {
            return 0;
        }
        int[] result = quickSort(a, n);
        return result[K-1];
    }
    
    // 快排的具体实现
    public static int[] quickSort(int[] a, int n) {
        // 判断数组的长度是否为 0 或者为 1
        if (0 == n || 1 == n) {
            return a;
        }
        // 荷兰国旗问题
        // 定义两个指针，分别指向小于区域末尾和大于区域头部
        int smP = -1;
        int lrP = n;
        // 定义一个指针
        int tempP = 0;
        // 定义一个辅助的整型变量
        int helpVal = a[n - 1];
        // 定义一个临时变量
        int tempVal = 0;
        while (tempP != lrP) { // 如果不满足该条件，证明已经完成了荷兰国旗问题，直接退出循环
            if (a[tempP] > helpVal) { // 小于
                // 先将该节点与小于区域右移一位的节点进行交换
                tempVal = a[tempP];
                a[tempP] = a[smP + 1];
                a[smP + 1] = tempVal;
                // 然后小于区域向右扩充
                smP++;
                tempP++;
            } else if (a[tempP] == helpVal) { // 等于
                // 啥都不要做
                tempP++;
            } else { // 大于
                // 先将该节点与大于区域左移一位的节点进行交换
                tempVal = a[tempP];
                a[tempP] = a[lrP - 1];
                a[lrP - 1] = tempVal;
                // 然后大于区域向左扩充
                lrP--;
            }
        }
        // 递归
        int[] left = null;
        int[] right = null;
        if (smP == -1) {
            left = quickSort(new int[]{}, 0);
        } else {
            left = quickSort(Arrays.copyOfRange(a, 0, smP + 1), smP + 1);
        }
        if (lrP == n) {
            right = quickSort(new int[]{}, 0);
        } else {
            right = quickSort(Arrays.copyOfRange(a, lrP, n), n - lrP);
        }
        for (int i = 0; i < left.length; i++) {
            a[i] = left[i];
        }
        for (int i = 0; i < right.length; i++) {
            a[lrP+i] = right[i];
        }
        return a;
    }
}