本文主要是介绍【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(N),打消了排序的念头，那么就只有hash了，因为hash可以在判断每个元素的时候O(1)内完成，我们以给定数组中的元素值作为下标值，在对应位置上做标记，表示该数出现了。这样空间复杂度很明显为O(N)，这又不满足空间复杂度的要求。还要用hash，还不想开辟额外的空间，那么好像只能在原数组上打主意了。由于要考虑缺失的整数，所以下标我们用下标0来存储1，依次类推。
但是在原数组上进行操作就有问题了，我们最后怎么进行区分呢？就是说我们通过什么来判断该数是缺失的呢？对于小于等于0的数怎么处理呢？
首先我们来看下怎么进行区分的事情。在得到当前元素值时，我们要去处理其所代表的下标所对应的元素，为了表示这个数出现了，我们就需要做下标记，那么怎么做标记呢？改成一个特殊的数？好像不行，因为该下标对应的元素的值也代表的是下标的信息，那怎么办？对于下标而言，其实最关键的是该值的绝对值的大小，负数我们可以将其视为正数。所以我们可以将其对应的数改为负数。但是这就会与数组初始时的负数混淆了，这就引申出第二个问题，就是小于等于0的元素怎么处理，看来要对数组进行预处理，将小于等于0的数改为其他数，其他的什么数呢？肯定要是正数，而且不能是在1-n范围内的正数，这个很明显。
说了这么多，看个例子吧。
总结下思路，初始的时候，数组中的元素都是正数，每个下标都可能会被映射一次，若被映射到，则将对应的元素的值改为负数，最终，为正数的表示其下标未被映射到，也就是对应的正整数没有出现。
int firstMissingPositive(int A[], int n) {if(n == 0)return 1;for(int i = 0; i < n; ++i){if(A[i] <= 0)//any number that > n is ok.A[i] = n + 2;}for(int i = 0; i < n; ++i){if(abs(A[i]) <= n){A[abs(A[i]) - 1] = -abs(A[abs(A[i]) - 1]);}}for(int i = 0; i < n; ++i){if(A[i] > 0)return i + 1;}return n + 1;}
这篇关于【leetcode】First Missing Positive的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
