• Here is my first implementation based on the top voted answer !

Maybe it seems no difference with the AC code, but my swap function is wrong !

``````class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int len=nums.size();

for(int i=0; i<len; i++){
if(nums[i]>0 && nums[i]<=len){
while(nums[i]!=nums[nums[i]-1])   swap(nums[nums[i]-1], nums[i]);
}
}

for(int i=0; i<len; i++){
if(nums[i]!=i+1)    return i+1;
}
return len+1;
}
};
``````

It failed for the case : [0,-1,3,1]

Because we swap 1 and 0 in the final and then nums[i]=0, so the nums[nums[i]-1] will cause the RE

Based on the wrong case, we change the code like this:

``````class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int len=nums.size();

for(int i=0; i<len; i++){
while(nums[i]>0 && nums[i]<=len && nums[i]!=nums[nums[i]-1])
swap(nums[nums[i]-1], nums[i]);
}

for(int i=0; i<len; i++){
if(nums[i]!=i+1)    return i+1;
}
return len+1;
}
};``````

• Move all the number to THE correct position in O(N).

Then just check one by one to find the first missing positive number.

Here is the code :

``````class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n=nums.size();
for(int i=0; i<n; i++){
/** check the nums[i] is valid and it is not in its right position **/
while(nums[i]>0 && nums[i]<=n && nums[i]!=nums[nums[i]-1])
swap(nums[nums[i]-1], nums[i]);
}

for(int i=0; i<n; i++){
if(nums[i]!=i+1)  return i+1;
}

return n+1;
}
};``````

• I think using the while loop is not easy to understand directly ......

Here are some tricks to use the while loop to swap the wrong-positioned-num-number with the correct number ..

Here is the AC C++ implementation

``````class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int size_nums = nums.size();
for(int i = 0; i < size_nums; i++) {
while(nums[i] > 0 && nums[i] <= size_nums && nums[nums[i]-1] != nums[i]) {
swap(nums[nums[i]-1], nums[i]);
}
}
for(int i = 0; i < size_nums; i++) {
if(nums[i] != (i+1))  return i+1;
}
return size_nums+1;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.