This link has a nice explanation of the problem. I rewrite the code below. Play with it using some special examples and you will find out how it works. Try the two on the problem statement and the following ones if you like: [0], [2], [-1, 1], [-1, 2], [1, 2].
1 class Solution { 2 public: 3 int firstMissingPositive(vector<int>& nums) { 4 int n = nums.size(); 5 for (int i = 0; i < n; i++) 6 while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) 7 swap(nums[i], nums[nums[i] - 1]); 8 for (int i = 0; i < n; i++) 9 if (nums[i] != i + 1) 10 return i + 1; 11 return n + 1; 12 } 13 };
