题解 | #寻找第K大#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param a int整型一维数组
 * @param n int整型
 * @param K int整型
 * @return int整型
 */
function findKth(a, n, K) {
    // write code here
    return divide(a, K);
}
function divide(array, k) {
    // 选择基准元素，这里我们选择数组中间的元素
    const pivotIndex = Math.floor(array.length / 2);
    //console.log(pivotIndex);
    const pivot = array[pivotIndex];

    // 初始化左右数组
    const left = [];
    const right = [];

    // 遍历除基准元素外的数组元素，根据比较结果将元素分配到左右数组中
    for (let i = 0; i < array.length; i++) {
        if (i === pivotIndex) {
            continue; // 跳过基准元素
        }

        if (array[i] < pivot) {
            //小于基准元素的填充到左数组
            left.push(array[i]);
        } else {
            //大于基准元素的填充到右数组
            right.push(array[i]);
        }
    }

    //如果k正好是基准元素所在位置，就返回基准元素
    //如果k > right.length+1，说明要找的元素在左边的数组
    //如果k < right.length+1，说明要找的元素在右边的数组
    if (k == right.length + 1) {
        return pivot;
    } else if (k > right.length + 1) {
        return divide(left, k - right.length - 1);
    } else {
        return divide(right, k);
    }
}
module.exports = {
    findKth: findKth,
};