LeetCode 41. 缺失的第一個正數

題目

給你一個未排序的整數數組，請你找出其中沒有出現的最小的正整數。

示例 1:

輸入: [1,2,0]
輸出: 3
示例 2:

輸入: [3,4,-1,1]
輸出: 2
示例 3:

輸入: [7,8,9,11,12]
輸出: 1           

提示：

你的算法的時間複雜度應為O(n)，并且隻能使用常數級别的額外空間。

解題思路

class Solution:
    def firstMissingPositive(self, nums: [int]) -> int:
        # maxNum = 0
        # contDic = {}#用字典方式存放已存在數值，周遊為O(1)
        # for i in nums:
        #     if i > maxNum:
        #         maxNum = i
        #     contDic[i] = 1
        # for j in range(1, maxNum):
        #     if j not in contDic:
        #         return j
        # return maxNum+1
        #空間複雜度O(1) 因為最小值隻存在于[1,n+1]中，中通過負号來标記值對應的index已經存在，如果[1,n]中存在正号，代表那個index未被周遊指派，為最小值
        maxNum = len(nums)
        for i in range(maxNum):
            if nums[i] <= 0:
                nums[i] = maxNum +1
        for j in nums:
            if abs(j) <= maxNum:#把值中對應的index變為負來進行标記
                # print(j)
                nums[abs(j)-1] = -abs(nums[abs(j)-1])
        # print(nums)
        for k in range(maxNum):
            if nums[k] >=0:
                return k+1
        return maxNum+1