1539. 第 k 个缺失的正整数.md

1539. 第 k 个缺失的正整数

• 哈希表

/**
 *
 * @complex T(n + k)/S(n + k)
 * @param {number[]} arr
 * @param {number} k
 * @return {*}  {number}
 */
function findKthPositive(arr: number[], k: number): number {
    const table: number[] = new Array(arr.length + k);
    for (let i = 0; i < arr.length; ++i) {
        const value: number = arr[i];
        table[value - 1] = value;
    }
    for (let i = 0; i < table.length; ++i) {
        !table[i] && k--;
        if (!k) return i + 1;
    }
    return -1;
};

• 直接遍历

/**
 *
 * @complex T(n + k)/S(1)
 * @param {number[]} arr
 * @param {number} k
 * @return {*}  {number}
 */
function findKthPositive(arr: number[], k: number): number {
    let lastMiss: number = 0,
        index: number = 0,
        currentValue: number = 1;
    for (let missCount: number = 0; missCount < k; ++currentValue) {
        if (arr[index] === currentValue) {
            ++index;
        } else {
            ++missCount;
            lastMiss = currentValue;
        }
    }
    return lastMiss;
};

• 二分法

// todo: