分享程序员开发的那些事...
更新时间：2021-10-25 19:33:45
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 };