41. First Missing Positive

📋 Đề Bài

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

You must implement an algorithm that runs in O(n) time and uses constant extra space.

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints:

1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

🧠 Thuật Toán & Kỹ Thuật

Sorting (Sắp xếp)

⏱️ Thời gian O(n log n)

💾 Không gian O(n)

💻 Lời Giải

Python 0041-first-missing-positive.py

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        nums = list(set(nums))
        step = 1
        
        nums.sort()
        
        for num in nums:
            if num <= 0:
                continue
            if num != step:
                return step
            step += 1
            
        return step