题目

给你一个未排序的整数数组 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

思路

题目要求On的时间复杂度和O1的空间复杂度
所以要做到原地处理数组，那么我们可以把对应数字存储到这个数字减1作为下标的位置上，最后从前往后遍历，找到第一个不匹配的，返回答案，注意在交换过程中能换就要一直换换到不能换为止，可以交换的条件是这个数字不是负数，负数没必要换，并且这个数字必须小于等于Len(nums）因为如果大于，没意义就算换出去也不会被取到也是取数组的最远位置作为值的，不会超出数组下标，要注意去重问题，这里有两种解决思路，一直是开个哈希表去一次重，问题就是空间复杂度大了，还有一种思路就是交换的时候如果有重复，就不换了把其中要换过去的那个置为-1

代码

def firstMissingPositive(self, nums):  
    def Swap(left,right):  
        if(nums[left] == nums[right]):  
            nums[left] = -1  
        temp = nums[left]  
        nums[left] = nums [right]  
        nums[right] = temp  
    for i in range(0,len(nums)):  
        while(nums[i] != i + 1 and nums[i] >= 1 and nums[i] <= len(nums)):  
            Swap(i,nums[i] - 1)  
    for i in range(0,len(nums)):  
        if(i +1 != nums[i]):  
            return i+1  
    return len(nums) + 1

def firstMissingPositive(self, nums):  
    nums = list(set(nums))  
    def Swap(left,right):  
        temp = nums[left]  
        nums[left] = nums [right]  
        nums[right] = temp  
    for i in range(0,len(nums)):  
        while(nums[i] != i + 1 and nums[i] >= 1 and nums[i] <= len(nums)):  
            Swap(i,nums[i] - 1)  
    for i in range(0,len(nums)):  
        if(i +1 != nums[i]):  
            return i+1  
    return len(nums) + 1