LeetCode 41 First Missing Positive
https://leetcode.com/problems/first-missing-positive/
题目分析
要求 O(n) 的时间复杂度，O(1) 的空间复杂度。
题目让我们找出最小的缺失的正整数，其满足两个条件即可：
- 该数数组中没有；
- 该数前面的正整数数组中都有。
由于不能对数组进行排序，我们得想办法存下一些信息来帮助我们判断以上两个条件。
简单想了一下，貌似不能分治，那就只好遍历咯？
我们设当前目标值为 t，即当前最小的缺失的正整数。
设想我们现在正在进行中间某步，现在有一个新的正整数值 x（非正整数直接忽略即可）需要处理：
- x < t，该值没有意义；
- x = t，条件一不再满足，如果 t+1 数组中不存在，则 t=t+1，否则的话一直加 1，直到找到一个不存在的值。
- x > t，当前目标值虽然还是目标值，但我们需要以某种方式标记 x 已经出现过。
其中情况 2 和 3 都要求我们能够查询某个值是否已经存在。
如果用 Hash 表来进行标记的话，唯一的问题是，我们只能有常数项个值。
看了下 Hint：
Think about how you would solve the problem in non-constant space. Can you apply that logic to the existing space?
哦，我们或许可以用数组的前面部分来当 Hash 表来用？
假设中间某步为第 i 步（从 1 开始），t 一定满足：t<i。
额，貌似不行啊。
时间已经过了很久了，爷决定屈服了。
高赞 #1
实际上我们的 Hash 表有常数项个即可，因为目标值一定不会大于数组长度，所以说 Hash 表的项的数目最多不超过数组长度。
这样的话，直接用一个等长度的数组做 Hash 表即可。
是这一步分析出了问题：
如果用 Hash 表来进行标记的话，
唯一的问题是，我们只能有常数项个值。
我们用 Hash 表来进行记录：
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int res = 1;
unordered_map<int,bool> store;
for(auto num : nums) {
if (num < res) continue;
if (num > nums.size()) continue;
if (num == res) {
res++;
while(store.find(res) != store.end()) res++;
} else {
store[num] = true;
}
}
return res;
}
};
104 ms & 66.4 MB
用 Hash 表来记录还是太浪费了。
换成数组：
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int res = 1;
vector<bool> store(nums.size()+1);
for(auto num : nums) {
if (num < res) continue;
// We don't care num that large then nums.size()
if (num > nums.size()) continue;
if (num == res) {
res++;
// We have to make sure res is in a proper range.
while(res < nums.size() + 1 && store[res]) res++;
} else {
store[num] = true;
}
}
return res;
}
};
96 ms & 66.3 MB
emmm，差别并不大。
高赞 #2
这个就太巧妙了，对我的实用价值不大，2333。
class Solution {
public:
int firstMissingPositive(int A[], int n) {
for(int i = 0; i < n; ++ i)
while(A[i] > 0 && A[i] <= n && A[A[i] - 1] != A[i])
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;
}
};