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)的时间，所以一般的排序方法都不能用，最开始我没有看到还限制了空间复杂度，所以想到了用哈希表来解，这个思路很简单，第一遍遍历数组把所有的数都存入哈希表中，并且找出数组的最大值，下次循环从1开始递增找数字，哪个数字找不到就返回哪个数字，如果一直找到了最大的数字，则返回最大值+1，代码如下：
// NOT constant space class Solution { public: int firstMissingPositive(int A[], int n) { if (n <= 0) return 1; unordered_map<int, int> m; int mx = A[0]; for (int i = 0; i < n; ++i) { if (A[i] > 0) { m[A[i]] = 1; mx = max(mx, A[i]); } } for (int i = 1; i <= mx; ++i) { if (m.find(i) == m.end()) return i; } return mx + 1; } };
但是上面的解法不是O(1)的时间复杂度，所以我们需要另想一种解法，既然不能建立新的数组，那么我们只能覆盖原有数组，我们的思路是把1放在数组第一个位置A[0]，2放在第二个位置A[1]，即需要把A[i]放在A[A[i] - 1]上，那么我们遍历整个数组，如果A[i] != i + 1, 而A[i]为整数且不大于n，另外A[i]不等于A[A[i] - 1]的话，我们将两者位置调换，如果不满足上述条件直接跳过，最后我们再遍历一遍数组，如果对应位置上的数不正确则返回正确的数，代码如下：
class Solution { public: int firstMissingPositive(int A[], int n) { int i = 0; while (i < n) { if (A[i] != i + 1 && A[i] > 0 && A[i] <= n && A[i] != A[A[i] - 1]) { swap(A[i], A[A[i] - 1]); } else { ++ i; } } for (i = 0; i < n; ++i) { if (A[i] != i + 1) return i + 1; } return n + 1; } };
本文转自博客园Grandyang的博客，原文链接：首个缺失的正数[LeetCode] First Missing Positive ，如需转载请自行联系原博主。