题解 | #最小的K个数#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param input int整型一维数组
 * @param k int整型
 * @return int整型一维数组
 */
function GetLeastNumbers_Solution(input, k) {
    // write code here
    if (k === 0) return [];
    if (k > input.length) return input;
    let stack = [];
    for (let i = 0; i < input.length; i++) {
        if (stack.length < k) {
			// 下面的插入元素是相同的逻辑，可以封装为函数
            let idx = getInsertIdx(stack, input[i]);
            if (idx === 0) {
                stack.unshift(input[i]);
            } else if (idx === stack.length + 1) {
                stack.push(input[i]);
            } else {
                stack.splice(idx, 0, input[i]);
            }
        } else {
            if (stack[0] > input[i]) {
                stack.shift();
                let idx = getInsertIdx(stack, input[i]);
                if (idx === 0) {
                    stack.unshift(input[i]);
                } else if (idx === stack.length + 1) {
                    stack.push(input[i]);
                } else {
                    stack.splice(idx, 0, input[i]);
                }
            }
        }
    }

    let res = [];
    while (stack.length) {
        res.push(stack.pop());
    }
    return res;
}

// 处理新元素插入位置
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 = {
    GetLeastNumbers_Solution: GetLeastNumbers_Solution,
};