[leetcode] 41. First Missing Positive

문제 설명

링크
정렬되어있지 않은 배열에서, 존재하지 않는 가장 작은 양수를 O(n), constant memory 사용으로 구하는 문제

접근

• res 을 1로 초기화 하고 배열을 돌며 res 와 같은 값이 나오면 1 을 증가시켜준다
• res 값에 변화가 없을 때 까지 반복

코드

    def firstMissingPositive(self, nums: List[int]) -> int:
        res = 1
        change = True
        while change:
            change = False
            for num in nums:
                if res == num:
                    res += 1
                    change = True
        return res

참고 - leetcode discussion 의 O(n)

    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
		
        for i in range(n):
            if nums[i] <= 0 or nums[i] > n:
                nums[i] = n + 1

        for i in range(n):
            abs_num = abs(nums[i])
            if abs_num > n:
                continue
            nums[abs_num - 1] = -abs(nums[abs_num- 1])

        for i in range(n):
            if nums[i] > 0:
                return i + 1
        return n + 1

• 값이 존재하면 그 값이 가리키는 인덱스의 값을 음수로 만듬
• 양수라는 건 값이 없다는 것
• 배열은 순서가 있으므로 first min value 만족
• for 문을 무조건 3번씩 돌아서 위의 내가 짠 코드보다 평균적으로 느리게 나오는 듯함