41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
示例 2：

输入：nums = [3,4,-1,1]
输出：2
示例 3：

输入：nums = [7,8,9,11,12]
输出：1  

提示：

1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1

---

直观的思路：哈希表

但是时间空间复杂度都是O(n)，空间复杂度不满足题目的要求

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        exists = collections.defaultdict(int)
        for i in range(len(nums)):
            exists[nums[i]] = 1
        
        for i in range(len(nums)+1):
            if exists[i+1] == 1:
                continue
            else:
                return i+1
        return len(nums)+1

改造当前数组为哈希表

数组长度为n，则数组中的数，如果存储的是[1,n], 则第一个缺失的数是n+1
否则缺失的数一定在[1,n]中的某一个。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            # 把非正数都改为一个特殊的数，注意0也要修改
            if nums[i] <= 0:
                nums[i] = n + 1
        
        
        for i in range(n):
            # 数有可能已经被前序循环修改为负数了
            num = abs(nums[i])
            if num <= n:
                # print(num, nums)
                # 可能有重复的数
                nums[num-1] = -abs(nums[num-1])
        
        for i in range(n):
            if nums[i] >= 0:
                return i+1
        
        return n+1

交换方式

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

        n = len(nums)
        for i in range(n):
            # 多次交换, 注意死循环
            while 0 <  nums[i] <= n:
                index = nums[i] - 1
                if nums[index] == nums[i]:
                    break
                else:
                    swap(nums, i, index)

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