41. First Missing Positive

[zeikar]

Problem link

https://leetcode.com/problems/first-missing-positive/

Problem Summary

배열이 있을 때 배열에 나오지 않은 가장 작은 양의 정수를 구하는 문제.

Solution

O(n) 으로 풀어야 하는데 생각보다 쉽지 않다.

키 포인트는 배열에 차례대로 자리가 있다고 생각하는 것이다.
즉, 1, 2, 3은 각각 배열의 0, 1, 2 인덱스에 차례로 들어 있어야 한다. 그러면 그 배열에서 nums[i] == i + 1이 되지 않는 처음 값이 나오지 않은 가장 작은 양의 정수가 된다.

첫 번째 예제로 보면 1, 3, 4를 각각 0, 2, 3번 인덱스로 넣는다고 하면 [1, -1, 3, 4] 가 되고 2가 나와야할 자리에 -1이 있으므로 답이 2가 된다.

위 알고리즘은 배열을 순회하면서 자신이 가야 할 자리의 수와 swap 하는 방식으로 구현할 수 있고 swap 한 다음에도 해당 수가 자리에 맞는지 while로 계속 돌면서 넣어주면 된다. 0 이하 및 배열 길이 초과하는 수는 무시한다.

Source Code

from typing import List


class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            while True:
                idx = nums[i] - 1

                if nums[i] <= 0 or nums[i] > len(nums) or nums[i] == nums[idx]:
                    break

                nums[idx], nums[i] = nums[i], nums[idx]

        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i + 1

        return len(nums) + 1