LC 41缺失的第一个正数First Missing Positive　困难

找出数组中未出现的最小正整数，要求 O(n) 时间、常数空间。

思路 原地哈希：把值 x 交换到下标 x-1 处，再扫第一个 nums[i] != i+1 的位置。时间 O(n)、空间 O(1)。

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