解题思路#

题解#

41. 缺失的第一个整数#

这一题很容易想到用一个长度为n的哈希表记录每个整数是否存在 但是难点在于要用常数级别的额外空间，所以我们想怎样在原数组的基础上标记 我们可以将对应元素移动到对应位置上去，但这样有点复杂 怎样在保证原有信息的情况下标记？ 我们可以通过位置上元素的正负解决，因为负数在题中是无用信息 依循这个思路，首先我们要排除无关元素的干扰，都把它们赋为特定正值 然后遍历数组，把存在的对应位置上的元素标记为负

for _, v := range nums{ 
	if v != 1000000 && v != -1000000{ 
		if nums[abs(v)-1]>0{ 
			nums[abs(v)-1] = 0 - nums[abs(v)-1]} } }

最后遍历一次得到答案