41. 缺失的第一个正数 - 力扣LeetCode给你一个未排序的整数数组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 105-231 nums[i] 231 - 1题目分析数组自身即为空间首先让我们确认一下答案的取值范围假设数组长度为n答案最小为1当且仅当由1~n 排列满整个数组时才能取到最大答案 n1因此答案的范围在[1, n1]。从最简单的部分开始思考当我们使用哈希表时最简单直接的解法无疑是先将所有数组中的元素存入哈希表中再从1~n 遍历一次寻找第一个不出现在哈希表中的元素假若遍历完了还没找到则说明答案取得 n1。为什么我们需要这么存数值再遍历因为我们需要按照数字顺序依次寻找哪个数字没有出现在数组中哈希表给了我们一个O1按序查询数字的方法。但这道题中数组长度为n答案取值为 1~n1我们完全可以将数字对应下标给排序进数组中排序过后只要遍历一遍数组查看数组的哪一个位置下标与元素对应关系消失就可以查找出最小缺失的正数而这也就是O1额外空间的思路。代码思路解析# 正确思路# 发现数组下标本身就是哈希表用原地置换代替外部存储。这是用下标编码信息的经典套路# 是这样的# 这题根本用不到哈希表只需要列表自身就能实现或者说列表本身就是哈希表# 我们需要确认最后的答案一定是在 [1n1]这个范围内# 列表长度为n 答案最大的情况下列表中全为正数且没有空缺答案是 n1# 其余列表中含有0/负数的情况下无论如何答案都小于 n1# 也就是说我们只要确认 1~n1 这 n 个数字中第一个缺失的正数是谁即可# 由于列表长度为n因此我们完全可以理由列表原地排序让正数和下标呈对应关系nums[0]1# 之后在遍历一次查找 nums[i] 1 ! i 的结果是谁即可# 排序规则1当前位置的元素不与下标呈对应关系 2当前位置元素属于[1, n1]范围内的数代码展示class Solution: def firstMissingPositive(self, nums: List[int]) - int: n len(nums) for i in range(n): x 1 while 1 nums[i] n and nums[nums[i]-1] ! nums[i]: temp nums[nums[i]-1] nums[nums[i]-1] nums[i] nums[i] temp for i in range(n): if nums[i] ! i1: return i1 return n1
