41. 缺失的第一个正数
https://leetcode-cn.com/problems/first-missing-positive/
解法一:
把所有正数i放到数组中第i-1个位置上,即理想情况应该是[1,2,3,...]
,然后从头遍历,找第一个不符合该条件的,就是没出现的最小正数。
难点在于怎么放。对于给定位置i,其值应该为i+1,同理对于给定值nums[i]
,其位置应该为nums[i]-1
从i=0开始遍历数组,若nums[i] == i+1
,符合该条件的不用修改;此外非正数也不用修改;还有位置超出数组长度的也不用修改。
若不满足nums[i] == nums[nums[i]-1]
,交换这两个数,将i处的数字放到合适位置,使其符合要求(为何用值来确定位置?因为位置是连续的从0~n-1,而值不一定能满足这些位置要求,所以只能根据值来定位)
其余情况直接跳过
此外交换时不能直接用a,b=b,a方式交换,因为下标嵌套了数组,交换过程中已经改变了相应的下标。应该写成函数来处理
最后更新于