数组缺失最小正整数C++解法 性能优化咨询

编写函数：

int solution(vector<int> &A);

该函数接收包含N个整数的数组A，返回A中不存在的最小正整数（大于0）。

示例：

• 给定A = [1, 3, 6, 4, 1, 2]，函数应返回5；
• 给定A = [1, 2, 3]，函数应返回4；
• 给定A = [-1, -3]，函数应返回1。

请编写满足以下约束的高效算法：

• N为取值范围在[1..100,000]的整数；
• 数组A中每个元素为取值范围在[-1,000,000..1,000,000]的整数。

我编写的如下解法正确性测试通过率为100%，但性能测试得分仅25%，请问如何改进以提升性能评级？

int solution(vector<int> &A) {
    int s=A.size();
    int x = 1;
    bool neg=true;
    for (int i=0; i<s;i++){     //check if all integers are negative
        if (A[i]>0){            
            neg = false;        
            goto check;
        }
    }
    check:
    if (neg==true){
        return x;     //returns 1 if all integers are negative
    }
    for (int i=0; i<s; i++){
        for(int j=0; j<s; j++){         
            if (A[j] == x ){
                x=A[j]+1;
                break;
            }
        }
    }
    return x;
}

问题原因与优化方案 #

性能差的核心原因 #

你的代码逻辑完全正确，但时间复杂度太高：

• 代码中用了两层嵌套循环遍历数组，整体时间复杂度为O(n²)
• 当数组长度达到题目上限100000时，双层循环需要执行上百亿次运算，远超出程序运行的时间阈值，因此性能测试无法通过。

优化思路 #

把「检查某个正整数是否存在」的操作从逐次遍历的O(n)复杂度降到O(1)，就能把整体时间复杂度降到O(n)，满足性能要求。最容易实现的方案是用哈希集合存储所有出现过的正整数，再从1开始依次递增检查，第一个不在集合里的数就是答案。

优化后的参考代码：

#include <unordered_set>
#include <vector>
using namespace std;

int solution(vector<int> &A) {
    unordered_set<int> pos_nums;
    for (int num : A) {
        if (num > 0) { // 负数和0不影响结果，直接跳过
            pos_nums.insert(num);
        }
    }
    int res = 1;
    while (pos_nums.count(res)) {
        res++;
    }
    return res;
}

如果需要进一步优化空间复杂度，还可以用原地哈希的方法，直接在原数组上标记正整数的存在状态，把空间复杂度降到O(1)，但上面的哈希写法逻辑简单、不易写错，已经可以拿到满分。

内容的提问来源于stack exchange，提问作者stackbik