---

(1)

因为至多只有n个数，故未出现最小正整数的最大为n+1，因此使用bool数组used[n+1]，used[i]记录数字i是否出现过，不在记录范围内的数字直接跳过。

(2)

int Solve(vector<int> &a)

{

    int n = a.size();

    vector<bool>used(n + 2, false);

    for(auto &value : a) {

        // 如果数字在记录范围内，则通过used记录value出现过

        if (value > 0 && value <= n)

            used[value] = true;

    }

    for(int i = 1; i <= n + 1; i++) {

        // 从最小正整数1开始遍历，直到找到第一个未记录的最小正整数

        if (!used[i])

            return i;

    }

}

 

(3)

时间复杂度O(n)，空间复杂度O(n)。

 

---