###### tags: `LeetCode`,`Python3`,`Hard`
# 41. First Missing Positive
### **題目連結：** [**First Missing Positive**](https://leetcode.com/problems/first-missing-positive/description/?envType=daily-question&envId=2024-03-26)

### **解題方向**
* 此題有限制時間為O(n)，空間為O(1)
* 嘗試將0<nums[i]<=len(nums)的值由小到大排序
* 排列成1,2,3...，也就是由1開始(index為0的位置要存放1)
* 在條件之外的數字就放到最後面，不用特別排序
* 接著再逐一比對nums[index]是否等於index+1，第一個錯的就回傳index+1，它就是遺失的最小正數
### **完整程式碼**

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        def swap(arr,i,j):
            arr[i], arr[j] = arr[j], arr[i]

        n=len(nums)
        for i in range(n):
            while 0<nums[i]<=n and nums[i]!=nums[nums[i]-1]:
                # 用while是因為換完一次後，新的nums[i]可能還是錯的，因此要一直重換
                swap(nums,i,nums[i]-1)
        
        for i in range(n):
            if nums[i]!=i+1:
                return i+1 # 回傳遺失的最小正數

        return n+1 # 此情況為整個list都是完整的，那n+1就會是遺失的最小正數