LeetCode 热题100-17 缺失的第一个正数
缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。
提示：
1 <= nums.length <= 10e5-2e31 <= nums[i] <= 2e31 - 1
可惜捏，只能想到用hashmap做个o(n)额外空间的做...(开辟空间了但是速度快hhh
class Solution:def firstMissingPositive(self, nums: List[int]) -> int: # Me！hashmap = {}for i in range(len(nums)):if nums[i] not in hashmap:hashmap[nums[i]] = 1 for i in range(len(nums)+1):if i+1 not in hashmap:return i+1想不到O n 1 的做法，看看大佬的做法吧，原地数组，将元素交换至（元素-1）下标的位置
随后从头往后寻找对应不起来的位置，然后返回就好了
class Solution:def firstMissingPositive(self, nums: List[int]) -> int: def swap(nums,a,b):tmp = nums[a]nums[a] = nums[b]nums[b] = tmp# 原地数组！nbfor i in range(len(nums)):while 1<=nums[i]<=len(nums) and nums[i]!=nums[nums[i]-1]:swap(nums,nums[i]-1,i)for i in range(len(nums)):if nums[i]!=i+1:return i+1return len(nums)+1