leetcode First Missing Positive

代码：

 1 #include<iostream>
 2 #include<vector>
 3 
 4 using namespace std;
 5 
 6 void swap(int &a, int &b)
 7 {
 8     int c = a;
 9     a = b;
10     b = c;
11 }
12 
13 int firstMissingPositive(vector<int>& nums) 
14 {
15     int L = nums.size();
16     int i = 0;
17     while (i < L)
18     {
19         if ((nums[i] - 1 >= L)||(nums[i] - 1 < 0) ||(nums[i] == i + 1) || (nums[i] == nums[nums[i] - 1]))
20             i++;
21         else
22             swap(nums[i], nums[nums[i] - 1]);
23     }
24     for (i = 0; i < L; i++)
25     {
26         if (nums[i] != i + 1)
27             break;
28     }
29     return i + 1;
30 }
31 
32 int main()
33 {
34     vector<int> nums = { 3, 4, -1, 1 };
35     cout << firstMissingPositive(nums) << endl;
36 }

分析：

循环起始：

当我们进入下标为i的位置时，有两种选择：

1（num[i]超出范围，num[i]==i）：i++；

2（num[i]!=i）:交换把num[i]放到num[num[i]]的位置上。

这两个选择做完后，i指向当前或i+1。如果i向下那么循环推进了；如果i没有推进仍然在i出那么总会把当前num[i]放在正确的位置，但是如果出现下面这种情况：

2 2 3 1 当前i==1（下标从1开始），就会出现死循环！！

所以if语句要写成上面这种情况。