[LeetCode] 41. First Missing Positive

해당 배열의 값을 활용하여 인덱스 비교를 통해 없는 값을 찾아내는 방법이다.

찾고자 하는 범위는 1~n까지만 조회하면 되므로 범위를 아래와 같이 잡았음

😎풀이

function firstMissingPositive(nums: number[]): number {
    const n = nums.length;

    // 1. 배열의 모든 음수와 0을 n+1로 대체 (필요 없으므로 1~n 범위를 조사함에 있어서 제외) 
    for (let i = 0; i < n; i++) {
        if (nums[i] <= 0 || nums[i] > n) {
            nums[i] = n + 1;
        }
    }

    // 2. 배열의 값을 인덱스로 사용하여 해당 값을 음수로 변환, 수가 있었음을 증빙하며 검색 대상에서 제외
    for (let i = 0; i < n; i++) {
        const num = Math.abs(nums[i]);
        if (num <= n) {
            nums[num - 1] = -Math.abs(nums[num - 1]);
        }
    }

    // 3. 다시 배열을 순회하여 첫 번째 양의 정수 탐색
    for (let i = 0; i < n; i++) {
        // 배열의 i번째 인덱스가 양수라면, i+1이 처음으로 누락된 양의 정수
        if (nums[i] > 0) {
            return i + 1;
        }
    }

    // 4. 모든 숫자가 존재하는 경우, n+1을 반환
    return n + 1;
}