LeetCode 41. First Missing Positive

Problem:

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

Example 1:

Input: [1,2,0]

Output: 3

 

Example 2:

Input: [3,4,-1,1]

Output: 2

 

Example 3:

Input: [7,8,9,11,12]

Output: 1

 

-Summary-

1. Set first positive integer as 1 --> posNum

2. loop-through the nums and check if posNum is in the nums list. (max int: 2^31 -1)

  - if there is, adding 1 more value to posNum and find the next positive number.

  - if not found, then return that value immediately.

다른사람이 푼 답을 보니 아래와 같은 방법으로도 풀수 있다.

leetcode.com/problems/first-missing-positive/discuss/17161/Python-O(n)-and-O(nlgn)-solutions.

Python O(n) and O(nlgn) solutions. - LeetCode Discuss

# O(nlgn) time
def firstMissingPositive(self, nums):
    nums.sort()
    res = 1
    for num in nums:
        if num == res:
            res += 1
    return res

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]