leetcode 41 缺失的第一个正数 TypeScript

leetcode 41 缺失的第一个正数 TypeScript

思路：
原地哈希 假设值为n，则将值为n的数换到数组下标index为n-1的位置
由于下标index>=0 且 index<arr.length，所以仅对正数、且在数组长度范围的值进行哈希
再通俗点说，1放到下标0位置，2放到下标1位置，…以此类推
最后从0遍历哈希表，如果缺失当前index对应的值index+1,直接返回结果即可

function firstMissingPositive(nums: number[]): number {
    const len = nums.length;
    for (let i = 0; i < len; i++) {
        // 原地哈希，将值 n 放到数组下标 index = n - 1 的位置
        while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] !== nums[i]) {
            [nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
        }
    }
    // 遍历查找对应位置
    for (let i = 0; i < len; i++) {
        if (nums[i] !== i + 1) return i + 1;
    }
    return len + 1;
};