今天是紀錄LeetCode解題的第四十一天
是一題困難題

第四十一題題目：Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

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

給定一個未排序的數組nums，傳回數組中不存在的最小正整數，需實作時間複雜度為O(n)且空間複雜度為O(1)

解題思路

遍歷整個nums，把數字換到正確的索引上(例如1到索引0、2到索引1)，判斷nums[i]是否在1 ~ n的範圍內(假設nums長度3，只要檢查nums[i]的範圍在1 ~ 3裡就好，如果大於 3 或<0的數字不會影響結果)且nums[nums[i] - 1] != nums[i] (避免一樣的數字重複交換)，換完位置之後檢查該數字是否在正確的索引上，如果不在的話就回傳該索引+1，如果都存在的話，例如nums=[1,2,3]，那麼就回傳n+1

程式碼

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

執行過程

初始狀態

• nums = [3,4,-1,1]
• n = 4

第一次執行交換(i=0)

• while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i] → True
• correct_idx = nums[i] - 1 = 2
• nums[i],nums[correct_idx] → nums[0] = -1 、 nums[2] = 3
• nums = [-1,4,3,1]
• while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i] → False

第二次執行交換(i=1)

• while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i] → True
• correct_idx = nums[i] - 1 = 3
• nums[i],nums[correct_idx] → nums[1] = 1 、 nums[3] = 4
• nums = [-1,1,3,4]

• while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i] → True
• correct_idx = nums[i] - 1 = 0
• nums[i],nums[correct_idx] → nums[0] = 1 、 nums[1] = -1
• nums = [1,-1,3,4]

第三次執行交換(i=2)

• while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i] → False

第三次執行交換(i=3)

• while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i] → False

第一次檢查(i=0)

• if nums[i] != i + 1 → nums[0] = 1 != 0 + 1 = 1 → False

第二次檢查(i=1)

• if nums[i] != i + 1 → nums[1] = -1 != -1 + 1 = 0 → True

最後結果

• 回傳i + 1 = 2，缺失的正整數答案為2