NC30 数组中未出现的最小正整数

方法一：暴力枚举

不难发现，对于长度为 $n$ 的 $arr$，最多包含 $n$ 个正整数，所以缺失的最小正整数 $x$ 必然满足 $1\le x\le n+1$。

一个很直观的思路是：枚举 $i\in [1,n+1]$，检查 $i$ 是否存在于 $arr$ 中。

时间复杂度：$O(n^2)$

空间复杂度：$O(1)$

class Solution {
public:int minNumberdisappered(vector<int>& arr) {int x = -1;for (int i = 1; i <= arr.size()+1 && anw == -1; i++) {bool find = false;for (int j = 0; j < arr.size() && find == false; j++) {if (arr[j] == i) find = true; }if (!find) x = i;}return x;}
};

方法二：哈希

方法一中，每查找一次 $i$ 的时间复杂度为 $O(n)$，考虑借助标记数组优化查找过程。

首先，定义长度为 $n+1$ 的标记数组 $mark$，并全部初始化为 false。$mark$ 的含义为：若 $mar{k}_i$ 为 false，则说明 $i+1$ 不存在，反之则存在。

std::vector<bool> mark(arr.size()+1, false);

接下来，遍历 $arr$，并更新 $mark$，该过程的时间复杂度为 $O(n)$。

for (auto d : arr) {if (1 <= d && d <= arr.size()+1) {mark[d-1] = true;}
}

考虑到答案的取值范围为 $[1,n+1]$，所以在更新过程中过滤了区间之外的值。这样在保证正确性的前提下，也避免了发生「访问数组越界」的问题。

最后，枚举$i\in [1,n+1]$，并检查 $mar{k}_{i-1}$ 是否为 false。每次检查的时间复杂度为 $O(1)$，整个检查过程的时间复杂度为 $O(n)$。

for (int i = 1; i <= arr.size()+1; i++) {if (mark[i-1] == false) {return i;}
}

整个过程的复杂度为：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

完整代码如下：

class Solution {
public:int minNumberdisappered(vector<int>& arr) {std::vector<bool> mark(arr.size()+1, false);for (auto d : arr) {if (1 <= d && d <= arr.size()+1) {mark[d-1] = true;}}for (int i = 1; i <= arr.size()+1; i++) {if (mark[i-1] == false) {return i;}}return -1;}
};

方法三：不使用标记数组的哈希

考虑到答案的取值范围为 $[1,n+1]$，因此将 $arr$ 中不在该区间的元素都置为 $n+2$ 也不会影响正确性。

for (auto &c : arr) {if (c < 1 || c > arr.size()) {c = arr.size()+2;}
}

经过上述处理后，$arr$ 中的元素均为正整数，那么可使用「正负」来表示某个数字是否存在：

• $ar{r}_i$ 为负表示数字 $i+1$ 存在于 $arr$ 中，反之不存在。
• $|ar{r}_i|$，即 $ar{r}_i$ 的绝对值才是 $ar{r}_i$ 真正的值。

接下来，再次遍历 $arr$，并更新 $arr$ 中个元素的正负。

for (auto c : arr) {int ori = abs(c); // 取出真正的值if (ori != arr.size()+2) {arr[ori-1] = -abs(arr[ori-1]); // 并将 arr[ori-1]置为负数。}
}

最后，遍历 $arr$，找出第一个满足 $ar{r}_i>0$ 的 $i$，则 $i+1$ 即为答案。如果不存在这样的 $i$，则答案为 $n+1$。

时间复杂度：$O(n)$

空间复杂度：$O(1)$

class Solution {
public:int minNumberdisappered(vector<int>& arr) {for (auto &c : arr) {if (c < 1 || c > arr.size()) {c = arr.size()+2;}}for (auto c : arr) {int ori = abs(c);if (ori != arr.size()+2) {arr[ori-1] = -abs(arr[ori-1]);}}for (int i = 0; i < arr.size(); i++) {if (arr[i] >= 0) {return i+1;}}return arr.size()+1;}
};