[LeetCode] 41. First Missing Positive

https://leetcode.com/

Given an unsorted integer array nums, return the smallest missing positive integer.

 

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

 

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

 

Example 2:

Input: nums =[3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

 

Example 3:

Input: nums =[7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

 

Constraints:

• 1 <= nums.length <= 10^5
• 2^31 <= nums[i] <= 2^31 - 1

 

Code :

var firstMissingPositive = function(nums) {
    const n = nums.length;

    // 1. 음수와 0을 n+1로 변경하여 처리합니다.
    for (let i = 0; i < n; i++) {
        if (nums[i] <= 0) {
            nums[i] = n + 1;
        }
    }

    // 2. 1부터 n까지의 숫자가 배열에 존재하는 경우, 해당 위치의 값을 음수로 변경합니다.
    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++) {
        if (nums[i] > 0) {
            return i + 1;
        }
    }

    return n + 1; // 1부터 n까지의 숫자가 모두 존재하는 경우
};

 

Solutions Code :

// Solution 1
var firstMissingPositive = function(nums) {    
    let m = new Map(); // 숫자들을 기록할 맵을 생성합니다.
    for (let i = 0; i < nums.length; i++) {
        m.set(nums[i], 1); // 배열의 숫자들을 맵에 기록합니다.
    }
    for (let i = 1; i <= nums.length; i++) {
        if (!m.has(i)) return i; // 1부터 nums.length까지의 숫자가 맵에 존재하지 않는 경우 해당 숫자를 반환합니다.
    }
    return nums.length + 1; // 배열이 [1,2,...,n]인 경우, n+1을 반환합니다.
    // 시간 복잡도: O(n)
    // 공간 복잡도: O(n)
    /*
    최악의 경우(처음으로 빠진 양의 정수가 가장 큰 경우)는 배열이 [1,2..,n]인 경우입니다. 
    따라서 이 경우를 제외하고는 첫 번째로 빠진 양의 정수는 n (nums.length)보다 작거나 같습니다.
    */
};

// Solution 2
var firstMissingPositive = function(nums) {
    // 우선, 빠진 가장 작은 양의 정수는 한 경우를 제외하고 n(배열의 길이)보다 작거나 같음을 이해해야 합니다. 이 설명은 위에서 언급된 바와 같습니다.
    // 우리는 배열에서 각 양의 정수를 해당하는 인덱스에 배치할 것입니다.
    // 예) 1은 인덱스 0에, 2는 인덱스 1에, 3은 인덱스 2에
    // 이 방법으로 배열은 주어진 배열의 크기를 변경하지 않고 n보다 작거나 같은 모든 정수를 해당하는 인덱스에 배치할 수 있습니다.
    // 따라서 우리는 배열을 검사하여 첫 번째 빠진 양의 정수를 찾을 수 있습니다.

    for (let i = 0; i < nums.length; i++) {
        let idx = nums[i]-1;
        if (i == idx || nums[i] == nums[idx]) continue; // 이미 위치가 정해진 경우이거나 nums[i]가 중복된 경우
        if (idx >= 0 && idx <= nums.length - 1) {
            [nums[i], nums[idx]] = [nums[idx], nums[i]]; // 두 위치의 숫자를 교환합니다.
            i--; // 교환된 숫자를 다시 검사합니다.
        }
    }
    
    for (let i = 0; i < nums.length; i++) {
        if (i+1 == nums[i]) continue; // 이미 위치가 정해진 경우이면 넘어갑니다.
        else return i+1; // i+1이 다음 양의 정수이며 배열에 존재하지 않습니다.
    }
    
    return nums.length + 1; // 배열이 [1,2,...,n]인 경우입니다.
    // 시간 복잡도: O(n)
    // 공간 복잡도: O(1)
};

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode