First Missing Positive

最后更新于:2022-04-01 22:58:03

**一. 题目描述** 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 #include using namespace std; class Solution { public: int firstMissingPositive(vector& 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; } }; ~~~
';