41.缺失的第一个正数（LeetCode热题100）

题目来源：

41. 缺失的第一个正数 - 力扣（LeetCode）

---

题目内容：

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。

---

思路分析：来源：41. 缺失的第一个正数 - 力扣（LeetCode）

鸽笼：

先加个数组代表鸽笼，原数组的值代表鸽子号，原数组值放到对应笼子，从笼子遍历，得到缺少的正整数，再分情况讨论，缺少的要么是1，要么是n+1 ，以及其中. 1以及其中的不需要考虑因为位于鸽笼里面，n+1特殊处理

---

代码实现： class Solution { public: int firstMissingPositive(vector<int>& nums) { int n=nums.size(); vector<int> aaa(nums.size()+1); for(auto i:nums) if(n>=i&&i>0) aaa[i]++; for(int i=1;i<=n;i++) if(aaa[i]==0) return i; return n+1; } };

---

题目心得： 很棒的一个思想，要积累一下。等到后面回过头来复习这些写过的题的时候，还要抽象出每道题的精华： 要么是用了很精妙的方法 要么是完整地诠释了有典型特征的某一类题型（也就是这一类的题目用固定的套路去解）有些函数/算法模板，不同的人用不同的实现方法，要积累出自己的，考试的时候又快又准的写出来