---

(1) 基本设计思想 (3分)

对于长度为 n 的数组，未出现的最小正整数一定在区间 [1, n+1] 之内。

算法思路：将每个在 [1, n] 范围内的元素 x 放到下标 x-1 的位置（即“就地哈希”）；最后从前往后扫描数组，第一个下标 i 使得 a[i] != i+1，则最小缺失正整数为 i+1；若全部匹配，则结果为 n+1。

 

 

---

 

(2) 算法描述 (C/C++，含关键注释) (8分)

 

int firstMissingPositive(vector<int>& a) {

    int n = a.size();

    // 将值 x 放到下标 x-1 上

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

        while (a[i] >= 1 && 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; // 全部匹配时

}

 

 

---

 

(3) 时间与空间复杂度分析 (2分)

 

时间复杂度：O(n)，每个元素最多交换一次，外加一次线性扫...