LeetCode题解——First Missing Positive

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

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.

解题思路：如果可以对数组排序就好解决了，但是排序的最少时间代价也要O(nlogn)，不满足题目要求。

那么换个思路。此题中真正有用的信息的是正数，如果我们将每个数都放在其应该放的位置，也就是说nums[i]放在位置nums[i]-1；然后再从头遍历数组，如果数组中的位置i 上的元素不为i+1；那么该元素就是最小的消失的正数。

例如：[ -1,4,1,7,2,-1]  ，将每个正数放到其应该放的位置的过程为：[ -1,4,1,7,2,-1]  ——>[ -1,7,1,4,2,-1] ——>[ 1,7,-1,4,2,-1] ——>[ 1,2,-1,4,7,-1] ——>end

遍历：i=2时 nums[i]!=i+1;所以First Missing Positive=3

程序如下：

class Solution {
public://将每个正数放在原本应该在的位置int firstMissingPositive(vector<int>& nums) {for(int i=0; i<nums.size();){if(nums[i]>0 && nums[i]<nums.size() && nums[i]!= i+1 && nums[nums[i]-1]!= nums[i]){swap(&nums[i],&nums[nums[i]-1]);}else i++;}for(int i=0; i<nums.size(); i++){if(nums[i]!=i+1)return i+1;}return nums.size()+1;}void swap(int* a, int* b){int temp = *a;*a = *b ;*b = temp;}
};

这篇关于LeetCode题解——First Missing Positive的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---