41. First Missing Positive

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

First Missing Positive - LeetCode

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        
        if 1 not in nums :
            return 1
        
        n = len(nums)
        
        for i in range(n) :
            if nums[i] <= 0 or nums[i] > n :
                nums[i] = 1
        
        for i in range(n) :
            ei = abs(nums[i])-1
            if nums[ei] > 0 :
                nums[ei] *= -1
        
        for i in range(n) :
            if nums[i] > 0 :
                return i+1
        
        return n+1
        

정리 :

이 문제는 추가 공간을 사용한다면 해쉬맵을 사용하여 충분히 쉽게 풀 수 있는 문제이다. 하지만 이 문제의 제약 조건이 추가 공간을 사용하지 않고 풀어야 한다는 것.

자, 차근차근 생각해보자. 우리가 구해야 할 것은 이 배열에 없는 가장 작은 양수이다. 그럼 우리는 0보다 작은 숫자들은 자연스럽게 무시할수 있다. 또 힌트를 더 찾아보자. 배열의 크기를 이용할 수 있을까? 그렇다. 우리는 배열의 크기를 이용해서 정답의 범위를 제한할 수 있다. 왜냐하면 배열의 크기가 n이라면 답은 최대 n+1일 수 밖에 없기 때문이다.

또 강조하고 싶은 점은, 배열을 사용할 때는 항상 index를 해쉬 키로 사용하여 풀 수 있다는 것.