LeetCode解題之First Missing Positive

原題

找出一個無序數組中缺少的最小的正整數。

注意點：

例子：

輸入: nums = [1, 2, 0]
輸出: 3

輸入: nums = [3,4,-1,1]
輸出: 2

解題思路

由於只需要找出缺少的第一個正整數，我們不妨把所有正數放到對應的位置，再找到第一個位置不匹配的地方原本應該放哪個數。如上面的例子[1,2,0]就已經排列好了，而[3,4,-1,1]應變為[1,-1,3,4]。分別遍歷這兩個數組，找到nums[i]!=i+1的位置，如果所有位置都符合，說明所有的數組成了從1開始的連續正整數。進行排列的方法就是依次遍歷每個數字，把它們放到應該放置的位子。

AC源碼

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 1
        i = 0
        length = len(nums)
        while i < length:
            current = nums[i]
            if current <= 0 or current > length or nums[current - 1] == current:
                i += 1
            else:
                nums[current - 1], nums[i] = nums[i], nums[current - 1]

        for i in range(length):
            if nums[i] != i + 1:
                return i + 1
        return length + 1


if __name__ == "__main__":
    assert Solution().firstMissingPositive([1, 2, 0]) == 3
    assert Solution().firstMissingPositive([1, 2, 3]) == 4
    assert Solution().firstMissingPositive([3, 4, -1, 1]) == 2

歡迎查看我的Python">Github來獲得相關源碼。