41. First Missing Positive

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

My Answer 1: Accepted (Runtime: 32 ms - 87.90% / Memory Usage: 14.5 MB - 17.45%)

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        if 1 not in nums:
            return 1
        
        for i in range(len(nums)):
            if nums[i] >= 2**31-1 or nums[i] <= -2**31:
                nums[i] = 0
                
        nums = list(set(sorted(nums)))  # 중복 제거
        result = 1
        
        # 양수만 저장
        nums = nums[nums.index(1):]
        
        for i in range(len(nums)):
            if result == nums[i]:
                result = nums[i]+1
            else:
                return result
        
        return result

1. 1 이 없으면 First Missing Positive 는 무조건 1 이므로 1 의 유무부터 확인
2. 가장 마지막 케이스가 [2147483647,2147483646,2147483645,3,2,1,-1,0,-2147483648] 이랬기 때문에... 이걸 통과시키기 위해서 범위 초과한 값들은 0 으로 바꿔주었다.
3. nums 를 중복 제거 + sort 한 후, 양수만 저장해줌
4. result 값을 1부터 1 씩 늘려가며 비교. result 랑 다른 값을 리턴해주면 됨

bucket Sort

Solution 1: Runtime: 24 ms - 99.32% / Memory Usage: 14.2 MB - 78.09%

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

bucket Sort 첨 들어봐서 가져왔다

양수는 1부터 시작하니까 모두 연속된 숫자면 1 ~ len(nums) 으로 구성됨
따라서 bucket 의 값이 0 이면 중간에 흐름이 끊긴 거니까 return
아니면 맨 마지막 값에 + 1 return

그 외 참고하면 좋은 솔루션들
https://leetcode.com/problems/first-missing-positive/discuss/336387/Python-different-solution