如何优化寻找数组中缺失的最小正整数的C#代码性能？

你的代码逻辑正确，但时间复杂度是O(n²)——因为每次调用A.Contains(hold)都会线性遍历整个数组，当数组规模达到10万级时，这种嵌套遍历会严重超时，这就是效率得分低的核心原因。

下面提供两种优化方案，都能把时间复杂度降到O(n)，满足大规模数组的性能要求：

方案一：哈希集合快速查找（实现简单，空间O(n)） #

利用HashSet的O(1)查找特性，先把所有正整数存入集合，再从1开始依次检查是否存在：

class Solution
{
    public static int solution(int[] A)
    {
        HashSet<int> positiveNumbers = new HashSet<int>();
        foreach (int num in A)
        {
            // 只存储正整数，负数和0对结果无影响
            if (num > 0)
            {
                positiveNumbers.Add(num);
            }
        }

        int smallest = 1;
        while (positiveNumbers.Contains(smallest))
        {
            smallest++;
        }
        return smallest;
    }
}

说明 #

• 遍历数组存入集合的时间是O(n)，后续查找每个数的时间是O(1)，整体时间复杂度O(n)
• 空间复杂度O(n)，对于10万元素来说，内存占用完全在合理范围内

方案二：原地标记法（空间O(1)，极致高效） #

如果对内存占用有严格要求，可以利用数组本身的索引来标记已存在的正整数，不需要额外空间：

class Solution
{
    public static int solution(int[] A)
    {
        int n = A.Length;

        // 第一步：把所有非正整数替换为n+1（因为缺失的最小正整数一定在1~n+1之间）
        for (int i = 0; i < n; i++)
        {
            if (A[i] <= 0)
            {
                A[i] = n + 1;
            }
        }

        // 第二步：标记存在的正整数——若num在1~n范围内，将对应索引(num-1)的元素设为负数
        for (int i = 0; i < n; i++)
        {
            int num = Math.Abs(A[i]);
            if (num <= n)
            {
                A[num - 1] = -Math.Abs(A[num - 1]);
            }
        }

        // 第三步：找到第一个正数的索引+1，就是缺失的最小正整数
        for (int i = 0; i < n; i++)
        {
            if (A[i] > 0)
            {
                return i + 1;
            }
        }

        // 若所有1~n的数都存在，返回n+1
        return n + 1;
    }
}

说明 #

• 三次遍历都是线性的，时间复杂度O(n)，空间复杂度O(1)（仅使用常量级额外空间）
• 以示例[1, 3, 6, 4, 1, 2]为例：
  1. 替换后数组仍为[1,3,6,4,1,2]（全为正整数）
  2. 标记后数组变为[-1,-3,-6,-4,1,-2]（索引4对应的值仍为正数，说明5不存在）
  3. 遍历到索引4时返回4+1=5，与预期结果一致

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