给你一个未排序的整数数组nums请你找出其中没有出现的最小的正整数。请你实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案。参考灵茶山艾府的解法写自己的理解方便记忆总体思路将每个数字放在与数字对应的位置上nums[ i ] i 1)最后遍历数组第一个位置与值不相符的数字就是没有出现的最小正整数第一步将数组中的每个数字都放在对应地位置上1对于一个长度为n的数组来说缺失的最小正整数一定在[1, n]范围内故1 i n是判断数字有效的条件之一2有效数字在数组中一定有目标位置判断目标位置的数字是否是正确的如果不正确就将当前的有效数字与目标位置的值交换直到当前位置数字无效最终处理后的数组内有效数字都处于对应地位置上其余位置上都是无效或者重复的数字class Solution: def firstMissingPositive(self, nums: List[int]) - int: n len(nums) for i in range(n): while 1 nums[i] n and nums[nums[i] - 1] !nums[i]: j nums[i] - 1 nums[i], j j, nums[i]为什么2不使用nums[ i ] ! i 1判断当前位置的数字是否是正确的因为如果当前位置和目标位置数字是重复且正确的就会陷入死循环即不断交换两个位置的数字第二步遍历有效数字第一个不在对应位置上的有效数字就是缺失的最小正数如果所有有效数字都在对应的位置上那么缺失的最小正数就是最大有效数字1for i in range(n): if nums[i] ! i 1: return i 1 return n 1