题解 | #寻找第K大#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param a int整型一维数组
 * @param n int整型
 * @param k int整型
 * @return int整型
 */
function findKth(a, n, k) {
    // write code here
    if (n === 0) return [];
    let stack = [];
    for (let i = 0; i < n; i++) {
        if (stack.length < k) {
			// stack长度小于k时 先填满stack
            let idx = getInsertIdx(stack, a[i]);
            if (idx === 0) {
                stack.unshift(a[i]);
            } else if (idx === stack.length + 1) {
                stack.push(a[i]);
            } else {
                stack.splice(idx, 0, a[i]);
            }
        } else {
			// stack长度等于k时，根据新的元素应该插入的位置 做不同处理
            let idx = getInsertIdx(stack, a[i]);
			// 在stack首位置插入，诞生了一个新的最大数，则第k大数易位，末尾砍掉
            if (idx === 0) {
                stack.unshift(a[i]);
                stack.pop()
            } else if (idx === stack.length + 1) {
 				// 在stack尾位置插入，说明该数小于当前第k大 什么也不用做
            } else {
			 	// 在stack中间位置插入，第k大数易位，移除尾部元素
                stack.splice(idx, 0, a[i]);
                stack.pop()
            }
        }
    }
    return stack.pop();
}

// 获取元素插入位置
function getInsertIdx(arr, num) {
    if (arr.length === 0) return 0;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] <= num) {
            return i;
        }
    }
    return arr.length + 1;
}
module.exports = {
    findKth: findKth,
};

和【BM46 最小的K个数】思路相同，维护一个顶根堆，长度为k，堆尾就是第k大的数