https://leetcode-cn.com/probl...题目测试评论给定一个正数数组nums，返回不在数组中的最小正整数。要求：时间复杂度O(n)，空间复杂度O(1)本题解法的巧妙之处在于输入数组用于标记，节省了额外空间的使用，从而实现了O(1)空间的复杂度.重点是：如果数组的长度是n，那么答案一定在[1,n+1]中。这是显而易见的，因为nums中只有n个数，[1,n+1]中的数不可能全部出现。如果要达到O(n)的时间复杂度，只能遍历，不能排序。这里的方法是处理特殊情况。如果1已经不在nums中，答案自然是1。否则：先把数组中除[1,n+1]以外的数去掉，因为它们根本不会影响结果，干脆把这些数写成1.那么，nums中只有正数，取值都在[1,n]之内。我们遍历数组，对数组中的每一个数，让nums对应位置的数为负数。把所有数字的位置都标出来了，相当于用了一个桶排序算法。然后再遍历，第一个不是负数的位置就是缺失的数。这里n需要特殊处理，因为n会越界，直接用位置0表示n，也可以把所有的数都减一。类解决方案：deffirstMissingPositive(self,nums:List[int])->int:if1notinnums:return1n=len(nums)foriinrange(n):ifnums[i]>nornums[i]<=0:nums[i]=1foriinrange(n):a=abs(nums[i])ifa==n:nums[0]=-abs(nums[0])else:nums[a]=-abs(nums[a])foriinrange(2,n):ifnums[i]>0:returnireturnnifnums[0]>0elsen+1欢迎来我的博客：https://codeplot.top/我的博客刷题分类：https://codeplot.top/categori...
