第一周 LeetCode41 First Missing Positive

本文主要是介绍第一周 LeetCode41 First Missing Positive，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

First Missing Positive

LeetCode上的41题：https://leetcode-cn.com/problems/first-missing-positive/description/

First Missing Positive
- 题目
- 题解
- 代码

题目

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Your algorithm should run in O(n) time and uses constant extra space.

题解

设数组长度为n，容易看出要找的最小的缺失正整数必然在1到n+1之间，如果数组的所有数在1到n之间，那么缺失的第一个正数为n+1，否则缺失的第一个正数在1到n之间。
如果不考虑空间的话可以使用一个大小为n的数组，然后遍历原数组，若元素值在1到n之间，则在数组对应该元素值的地方（元素值减一）做记录。最后遍历新的数组，找到第一个没有做记号的位置，返回下标加一。若没有找到说明原数组的元素值都在1到n之间，那么答案为n+1

但是题目要求使用常数空间，故不能使用新的数组，而是要在原数组上进行修改。方法和上面基本一样，当扫描到元素值在1到n之间的数，若其位置不对则将其放在对应位置上。在第二个例子，遍历到3时将3和位置2的数交换，得到[-1, 4, 3, 1]，当元素值不在1到n之间，或是该元素位置正确则继续遍历。

此时需要处理一种特殊情况，如数组[2, 2]，当遍历第一个2时将其与位置1的数交换，但交换的也是2，导致死循环，因此交换时需要测试交换的两个数是否相等。这个条件如果成立，说明该元素对应的位置已经放置了正确的数，不用交换继续遍历。

代码

class Solution {
public:int firstMissingPositive(vector<int>& nums) {int k = 0, _size = nums.size();while (k < _size) {if (nums[k] > 0 && nums[k] < _size + 1 && nums[k] != nums[nums[k] - 1]) {swap(nums[k], nums[nums[k] - 1]);}else {k++;}}int j = 0;for (; j < _size; j++) {if (nums[j] != j + 1)return j + 1;}return j + 1;}
};