**一. 题目描述** Given an unsorted integer array, find the first missing positive integer. For example,  Given `[1,2,0]` return `3`,  and `[3,4,-1,1]` return `2`. Your algorithm should run in O(n) time and uses constant space. **二. 题目分析** 该题的大意是给定一个未排序的数组，该数组可能包含零或正负数，要求找出第一个未出现的正数。例如`[1, 2, 0]`，由于第一个未出现的正整数是`3`，则返回`3`；`[3, 4, -1, 1]`第一个未出现的正整数是`2`，则返回`2`。算法要求在`O(n)`的时间复杂度及常数空间复杂度内完成。 一种方法是，先把数组里每个正整数从`i`位放到第`i-1`位上，这样就形成了有序的序列，然后检查每一下标`index`与当前元素值，就能知道当前下标所对应的正整数是否缺失，若缺失则返回下标`index + 1`即可。 **三. 示例代码** ~~~ #include <iostream> #include <vector> using namespace std; class Solution { public: int firstMissingPositive(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n; ++i) { int temp = 0; while (i + 1 != nums[i] && nums[i] != nums[nums[i] - 1] && nums[i] > 0) { temp = nums[i]; nums[i] = nums[temp - 1]; nums[temp - 1] = temp; } } for (int i = 0; i < n; ++i) { if (i + 1 != nums[i]) return i + 1; } return n + 1; } }; ~~~