力扣刷题Day 42：缺失的第一个正数（238）

1.题目描述

2.思路

方法1：把原数组转化成集合，然后从1开始递增查询当前正整数是否在集合里。

方法2：将原数组进行排序，删除非正数，再在数组头部加入元素0， 遍历数组就可以找出其中没有出现的最小正整数。

方法3：灵茶山艾府大佬的换座位思路，一个萝卜一个坑，非常巧妙。

3.代码（Python3）

方法1：

class Solution:def firstMissingPositive(self, nums: List[int]) -> int:nums = set(nums)min_miss = 1while 1:if min_miss not in nums:return min_missmin_miss += 1

方法2：

class Solution:def firstMissingPositive(self, nums: List[int]) -> int:nums.sort()while nums[0] <= 0:nums.pop(0)if not nums:return 1nums.insert(0, 0)for i in range(1, len(nums)):if nums[i] != nums[i - 1] + 1 and nums[i] != nums[i - 1]:return nums[i - 1] + 1return nums[-1] + 1

方法3：

class Solution:def firstMissingPositive(self, nums: List[int]) -> int:n = len(nums)# 换座位for i in range(n):while (1 <= nums[i] <= n) and nums[i] != nums[nums[i] - 1]:j = nums[i] - 1nums[i], nums[j] = nums[j], nums[i]# 是否匹配for i in range(n):if nums[i] != i + 1:return i + 1return n + 1

4.执行情况

方法1：

方法2：

方法三：

5.感想

不知道方法1算不算是使用了常数级别的额外空间，而且我天呢被方法3绕晕了我不是开玩笑，直接nums[i] - 1 != i不行，去了j = nums[i] - 1也不行T_T