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) :
            t = abs(nums[i])
            if t <= n :
                nums[t-1] = -abs(nums[t-1])
                
        for i in range(1, n+1) :
            if nums[i-1] > 0 :
                return i
            
        return n+1
            

1. invalid한 값들을 1로 변경.

2. 해당 인덱스의 값을 음수로 변경.

3. 배열을 순회하면서 인덱스의 값이 양수인 지점에서 i를 리턴.

 

정리 :

extra space를 사용할 수 없다면 배열 자체를 수정. 이에 대한 좋은 대안은 인덱스를 해쉬 키 값으로 사용하는 것. 그리고 음수와 양수로 해당 값에 특정한 의미를 부여.