数组中未出现的最小正整数

leetcode: First Missing Positive

首先先拿出最强方法：

class Solution(object):
    def firstMissingPositive(self, nums):
        L = 0
        R = len(nums)
        while L < R:
            if nums[L] == L + 1:
                L += 1
            elif nums[L] > R or nums[L] <= 0 or nums[L] == nums[nums[L]-1]:
                R = R - 1
                nums[L], nums[R] = nums[R], nums[L]
            else:
                tmp = nums[L] - 1
                nums[L], nums[tmp] = nums[tmp], nums[L]

        return L + 1

# 测试用例
s = Solution()
print s.firstMissingPositive([3,4,-1,1])
print s.firstMissingPositive([2,1])
print s.firstMissingPositive([2,2])

以上方法，可以达到时间复杂度O(n)，空间复杂度O(1)。

下面来解释一下

首先，数组里给的数字有正数，负数，0。

如果全部都是正数，那么未出现的最小正整数有三种可能
1. 如果长度为10，1到10之间的数字都出现过仅一次，那么最小未出现的数字就是11；如果所有的数字都属于0到10，但是某个数字出现了多次，那么未出现的正数一定在1到10之间。因为就10个坑，有个数多出现了一次，那么必定有个坑没数。
2. 如果除了有1到10之间的数字，还有其他10之后的数字出现，那么未出现的数字必定在1到10之间的某个数字没有出现过。

代码：

设置左右两个变量，L = 0 从最左边开始，R= 数组的长度，从最右边往左走

结束条件是L 和R 相遇。

下面开始 if 判断一些情况：

如果数字是这样的
```
数组下标 0    1    2    3    4
```
数值 1 2 3 4 5

那么这个数组的未出现整数的最大值就是6。
- 所以第一个if ，如果数字下标加一和数组[下标]表示的数字相等的话，我们就可以让L右移动一格，如果不相等的话，我们这个时候判断这几种情况：
- elif:
1.此时的数字是大于数组长度的，这样无效，可以直接丢弃，因为，这样的话，未出现的正整数必定在1到数组长度之间，绝对会缺少一个数字。我们只需要让R 左移动，因为这组数字的未出现的正整数绝对不可能是R+1。只可能是1到R，因为空出了一个坑。

2.如果此时的数字小于0，同理，R减一，又会缩小一个值。

3.如果此时的值在L左边出现过的话，我们就R-1，它也是一个无效的值，必定又多了一个坑。
- else:
  
  如果这个数字以前没有出现过，也在现在的有效的范围内的话，我们可以先交换这些数字，把他合理归为，比如，一个数组长度为10，现在L=2 R=8，此时的数字nums[L] = 5 ,那么我们就可以进行交换
  
  nums[5-1],nums[L] = nums[L], nums[5-1]，交换完成后L和R并没有变化，继续判断，是否是有效的值，进行循环。最终结果就是 L+1。

第二种思路

算法复杂度O(n), 空间复杂度未知O(max(nums))

就不贴了，用hashmap 来存储每个值，然后从小到大遍历一遍，来得到第一次未出现的那个正数。

另一种算法复杂度O(nlogn),空间复杂度O(1)

先进行排序，然后一个一个遍历。