Description
给定一个长度为\(n\)的数组\(a\)，返回其中缺失的最小正整数。
要求时间复杂度\(O(n)\)，空间复杂度\(O(1)\)。
Constraints
\(1 \le n \le 10^5\)
Solution
使用置换法，将数值\(i\)放到下标\(nums[i]\)里面，但只处理容器范围内的合法数值。
由于每次交换必能使其中一个位置正确归位，至多交换\(n\)次，因此时间复杂度是\(O(n)\)。
由于还有off-by-one问题，因此需要修正一下偏移量，使得范围统一为\([1, n]\)。
关联：287。
Code
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
auto off = nums.data() - 1;
auto n = nums.size();
for(int i = 1; i <= n; ++i) {
while(off[i] >= 1 && off[i] <= n
&& off[i] != off[off[i]])
swap(off[i], off[off[i]]);
}
for(int i = 1; i <= n; ++i) {
if(off[i] != i) return i;
}
return n+1;
}
};