**一. 題目描述** 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; } }; ~~~