备战春招：把之前碰到过的宇宙条面试题翻出来做一下，顺手做个记录
题目：
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
说明:
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
（从leetcode搬来的原题）
算法：
本质上还是常用的哈希表的思想，遍历数组时把数组元素放入一个哈希表并记录出现次数/出现与否，遍历完之后检查哈希表得到所求的值，在时间复杂度和空间复杂度的要求下再严格一点，在数组本身就对每个元素的出现情况做好常数级别的记录
具体分析起来，首先，假设数组长度为n，缺失的第一个正数，理论上所求的值应该是[1,n+1],那么通过这个特性在数组长度里可以存放所有可能结果的存在与否情况，具体方式也就是通过数组元素的索引序号来记录该值是否存在(真的很巧妙，感觉自己木头脑袋想不出来)。
代码：
具体到代码还是要好好操作一下，看过题解自己动手写多几次才是真的面试用得上
代码量还是不大的，好像写的有那么一点凌乱，稍微讲一下过程：
1.拿到数组长度，很简单
2.第一次遍历，把数组走一遍，看看有没出现1，没有的话返回1。这个处理是为了方便后面置1操作
3.第二次遍历，对数组里的非正数和大于数组长度的数全部置为1。因为他们都不可能是我们所要返回的值
4.第三次遍历，对数组里的值取绝对值，判断是否等于数组长度值，是的话对第0下标的值取负数，否则，对这个绝对值作为下标的值取负。这一步是主要算法了，理解一下就是，在前面处理完非正数和大于n的数之后，数组内的数只可能是1-n了，那么只要1-n出现，就对这个1-n的索引的值取负。也就是说假如(1,2,0)，处理了之后变成了（1，2，1），那么在这一次遍历中，1出现了且不为n，那么a[1]也就是2就要取反为-2，第二次进入循环，此时前面把这个第二个元素变成了-2，但是做了取绝对值的操作，保障了判断，所以等于2出现了（事实是本身它也出现了，只不过我们前面把它取反了，所以取绝对值操作就理解为取反操作带来的伴生操作吧）
5.第四次遍历，从第二个元素开始遍历到尾，如果有元素值为正，那么返回这个元素的索引。关键点，因为第一个元素用来记录数组长度n是否出现了，所以应该从1开始找，如果没有，再来判断第一个元素，也就是步骤6
6.上述5没有返回值的话，检查第一个元素a[0]，大于0的话返回数组长度n.
7.上述5，6都没有返回值的话，返回n+1
（ps:花了一个多小时写这个记录，感觉就算理解了解释起来文字还是挺费劲的，还是结合代码体会8，不行的话上leetcode官方有结合图示的应该比较好懂）
