寻求Codility最小未出现正整数O(n)解法优化，解决长数组报错问题

问题描述 #

给定包含N个整数的数组A，需返回数组中未出现的最小正整数（大于0），要求时间复杂度为O(n)。示例：输入A = [6, 4, 3, -5, 0, 2, -7, 1]，输出为5，因5是数组中未出现的最小正整数。

我的现状 #

• 方案1：表现稳定，在Codility演示测试中拿到了100分，但依赖外部库且时间复杂度为O(n log n)，不符合题目要求的O(n)时间限制
• 方案2：尝试实现O(n)逻辑，但输入包含负数的长度为10005的混乱序列时会报错，需要优化

优化方案（O(n)时间 + O(1)空间） #

核心思路是利用数组本身作为哈希表：我们要找的最小正整数一定在[1, N+1]范围内（如果数组包含1到N的所有数，答案就是N+1）。所以可以把每个有效的正整数放到它对应的索引位置（比如数字x应该放在索引x-1处），之后遍历数组就能快速找到缺失的最小正整数。

代码实现（以Python为例）

def find_smallest_missing_positive(A):
    n = len(A)
    for i in range(n):
        # 只处理1到n之间的数，且确保当前数不在正确位置，同时避免重复交换死循环
        while 1 <= A[i] <= n and A[A[i] - 1] != A[i]:
            # 交换当前数到正确的位置
            target_idx = A[i] - 1
            A[i], A[target_idx] = A[target_idx], A[i]
    
    # 遍历数组找第一个不符合的位置
    for i in range(n):
        if A[i] != i + 1:
            return i + 1
    # 如果所有1到n都存在，返回n+1
    return n + 1

关键细节说明

1. 过滤无效值：只处理1 <= x <= n的数，负数、0、大于n的数都不需要移动（因为它们不可能是我们要找的最小正整数，或者已经超出了[1, n]的范围）
2. 避免死循环：交换前检查A[A[i]-1] != A[i]，防止重复数字导致无限交换（比如数组里有两个2）
3. 原地操作：不需要额外的哈希表或集合，空间复杂度为O(1)，完美适配大数组（比如长度10005的情况）
4. 时间复杂度：每个元素最多被交换一次，整体时间复杂度是O(n)，完全符合要求

测试验证

• 示例输入[6,4,3,-5,0,2,-7,1]：处理后数组变为[1,2,3,4,0,6,-7,-5]，遍历到索引4时发现A[4] != 5，返回5
• 输入全负数[-3,-1,-5]：遍历后数组不变，第一个位置A[0] != 1，返回1
• 输入包含1到n的数组[1,2,3,4]：遍历后数组完全匹配，返回5

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