Example Example 1:
Input:[1,2,0] Output:3 Example 2:
Input:[3,4,-1,1] Output:2 Challenge Your algorithm should run in O(n) time and uses constant space.
解法1：类似bucket sorting。 这题的意思就是给一个unsorted array，长度N。问从1…N里面那个数字最先missing。要求时间复杂度O(n)，空间复杂度O(1)。所以不能用sort, hashmap之类的算法。 基本思想类似count sort，即把每个元素k尽量排到A[k-1]的位置，所以这里必须有一个内部的while loop。 关于这个时间复杂度，为什么是O(n)呢？看了网上很多类似的答案，好像都讲的不是太清楚。有知道的网友麻烦回复一下。不胜感激。
代码如下：
class Solution { public: /** * @param A: An array of integers * @return: An integer */ int firstMissingPositive(vector<int> &A) { int N = A.size(); if (N == 0) return 1; for (int i = 0; i < N; ++i) { while(A[i] > 0 && A[i] <= N && A[i] != i + 1) { if (A[A[i] - 1] == A[i]) break; //important! swap(A[i], A[A[i] - 1]); } } for (int i = 0; i < N; ++i) { if (A[i] != i + 1) return i + 1; } return N + 1; } };解法2：负数标记法。 原理就是把负数和0都标记为n+1，这样就不用考虑它们了。 然后扫描数组，如果遇到绝对值在1…n之内的数，比如说k，则将对应的nums[k-1]变成负数。这样的好处是没有冲掉num[k-1]的值，而且又可以利用其正负值来表示对应位是不是已经有了：负数表示已有，正数表示有。 举例: nums = [2,3,5,-1], n=4 一开始会把-1变成5，也就是nums=[2,3,5,5]。 处理完后nums = [2, -3, -5, 5] i=0, 遇到2，其绝对值在1…4内，将nums[2-1]=3变成-3。 i=1, 遇到-3，其绝对值仍然在1…4内，将nums[3-1]=5变成-5。 i=2, 遇到-5, 其绝对值不在1…内，不动 i=3, 遇到5，其绝对值不在1…内，不动 最后扫描nums，碰到的第一个>0的元素就是nums[0]=2，所以返回0+1=1。 实际上我们扫描整个数组，还可以发现nums[3]=5>0，所以下一个missing的正整数就是3+1=4。
class Solution { public: int firstMissingPositive(vector<int>& nums) { int n = nums.size(); if (n == 0) return 1; for (auto & it : nums) { if (it <= 0) it = n + 1; } for (auto & it : nums) { int abs_it = abs(it); if (abs_it <= n) nums[abs_it - 1] = -abs(nums[abs_it - 1]); } for (int i = 0; i < n; ++i) { if (nums[i] > 0) return i + 1; } return n + 1; } };