First Missing Positive
首先，实在受不了微信公众号后台对markdown的支持，查找了很多关于微信公众号排版的文章，包括池建强老师在知乎上地回答，池老师说微信后台对于代码的支持很差，真是深有体会。
从这篇文章开始，在文章中只提供文章题目的引用描述，题解移动到查看原文中，请各位见谅。
今天是一道在LeetCode上标记为Hard的题目，Acceptance为22.9%的题目，虽然知道思路之后会发现其实较为简单。
题目如下：
Given an unsorted integer array, find the first missing positive integer.
For example,Given[1,2,0]return3,
and[3,4,-1,1]return2.
Your algorithm should run in O(n) time and uses constant space.
其实，如果题目中不限制constant space，可以很容易解决这个问题，只要使用一个HashMap<Integer, Boolean>记录每一个数字是否出现过，然后从1开始，用HashMap.get(Integer)，当获得的值是null时，就是我们要找的值。
但是题目中限制了必须使用constant space，就不能采用这种方法，那么应该怎么做呢。
思路如下：
数组本身也可以作为一个map使用，即以数组的下标为键，以该下标的值为map的值，这样就可以把数组当做是map来看。代码如下：
C++版
class Solution
{
public:
int firstMissingPositive(int A[], int n)
{
for(int i = 0; i < n; ++ i)
while(A[i] > 0 && A[i] <= n && A[A[i] - 1] != A[i])
swap(A[i], A[A[i] - 1]);
for(int i = 0; i < n; ++ i)
if(A[i] != i + 1)
return i + 1;
return n + 1;
}
};
java
public class Solution {
public int firstMissingPositive(int[] nums) {
for(int i = 0; i < nums.length; i++){
if(nums[i] != i + 1){
int num = nums[i];
while(num < nums.length + 1 && num > 0 && nums[num - 1] != num){
int temp = nums[num - 1];
nums[num - 1] = num;
num = temp;
}
}
}
for(int i = 0; i < nums.length; i++){
if(nums[i] != i + 1)
return i + 1;
}
return nums.length + 1;
}
}
如果觉得文章有帮助的话，不妨关注一下本公众号，当然也希望能帮作者推广一下，更多人关注我也会更有动力，在此先谢过了。
关注我
image
