AC107-寻找缺失的最小正整数¶

给定一个含 n 个整数的数组，设计一个时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如：数组 {-5, 3, 2, 3} 中未出现的最小正整数是 1；数组 {1, 2, 3} 中未出现的最小正整数是 4。（2018 年统考题）

标准代码以及原地哈希代码[[#2. 原地哈希优化版本（空间O(1)）]]

代码实现¶

C
/**
 * 找出数组中未出现的最小正整数
 * @param A[] 输入数组
 * @param n   数组长度
 * @return    未出现的最小正整数
 */
int func(int A[], int n) {
    // 创建辅助数组B，用于标记1到n的正整数是否出现
    // B[i]表示正整数i是否在数组A中出现
    int *B = (int *)malloc(sizeof(int) * (n + 1));

    // 初始化辅助数组，所有位置都标记为未出现(0)
    for (int i = 0; i < n + 1; ++i) {
        B[i] = 0;
    }

    // 遍历原数组，标记出现的正整数
    for (int i = 0; i < n; ++i) {
        // 只处理范围在[1, n]内的正整数
        // 因为缺失的最小正整数必定在[1, n+1]范围内
        if (A[i] > 0 && A[i] <= n) {
            B[A[i]] = 1;  // 标记该正整数已出现
        }
    }

    // 从1开始查找第一个未出现的正整数
    for (int i = 1; i < n + 1; ++i) {
        if (B[i] == 0) {  // 如果正整数i未出现
            return i;     // 返回结果
        }
    }

    // 如果1到n都出现了，则缺失的最小正整数是n+1
    return n + 1;
}

算法执行过程图解¶

示例1：数组{-5, 3, 2, 3}¶

Text Only

输入数组A: [-5, 3, 2, 3]  n=4

步骤1: 创建辅助数组B[5]并初始化为0
B: [0, 0, 0, 0, 0]
    ↑  ↑  ↑  ↑  ↑
    0  1  2  3  4

步骤2: 遍历A数组标记出现的正整数
i=0: A[0]=-5 → 不在[1,4]范围内，跳过
i=1: A[1]=3  → 在范围内，B[3]=1
i=2: A[2]=2  → 在范围内，B[2]=1  
i=3: A[3]=3  → 在范围内，B[3]已为1，不变

B: [0, 0, 1, 1, 0]
    ↑  ↑  ↑  ↑  ↑
    0  1  2  3  4

步骤3: 查找第一个未出现的正整数
i=1: B[1]=0 → 找到未出现的正整数1
返回结果: 1

示例2：数组{1, 2, 3}¶

Text Only

输入数组A: [1, 2, 3]  n=3

步骤1: 创建辅助数组B[4]并初始化为0
B: [0, 0, 0, 0]
    ↑  ↑  ↑  ↑
    0  1  2  3

步骤2: 遍历A数组标记出现的正整数
i=0: A[0]=1 → B[1]=1
i=1: A[1]=2 → B[2]=1
i=2: A[2]=3 → B[3]=1

B: [0, 1, 1, 1]
    ↑  ↑  ↑  ↑
    0  1  2  3

步骤3: 查找第一个未出现的正整数
i=1: B[1]=1 → 已出现
i=2: B[2]=1 → 已出现
i=3: B[3]=1 → 已出现

所有1到3都出现了，返回n+1=4
返回结果: 4

复杂度分析¶

时间复杂度：O(n)¶

详细分析：

初始化辅助数组：
循环 n+1 次
时间复杂度 O(n)
标记出现的正整数：
遍历原数组 n 次
每次操作为常数时间
时间复杂度 O(n)
查找缺失的正整数：
最多循环 n 次
时间复杂度 O(n)
总体时间复杂度：O(n)

空间复杂度：O(n)¶

详细分析：

辅助数组B：
大小为 n+1
空间复杂度 O(n)
其他变量：
只使用常数个额外变量
空间复杂度 O(1)
总体空间复杂度：O(n)

关键知识点延伸¶

1. 算法核心思想¶

数学原理¶

对于长度为n的数组，缺失的最小正整数必定在[1, n+1]范围内
如果数组包含1到n的所有正整数，则答案是n+1
否则答案是1到n中第一个缺失的正整数

哈希表思想¶

使用辅助数组作为哈希表，下标表示数值，值表示是否出现
实现O(1)时间的查找和标记

2. 原地哈希优化版本（空间O(1)）¶

C
/**
 * 原地哈希版本 - 空间复杂度O(1)
 * 利用数组下标作为哈希表
 */
int firstMissingPositive(int A[], int n) {
    // 第一步：将所有非正数和大于n的数替换为n+1
    for (int i = 0; i < n; i++) {
        if (A[i] <= 0 || A[i] > n) {
            A[i] = n + 1;
        }
    }

    // 第二步：使用数组本身作为哈希表
    for (int i = 0; i < n; i++) {
        int num = abs(A[i]);
        if (num <= n) {
            // 将对应位置的数标记为负数（表示已出现）
            A[num - 1] = -abs(A[num - 1]);
        }
    }

    // 第三步：找到第一个正数的位置
    for (int i = 0; i < n; i++) {
        if (A[i] > 0) {
            return i + 1;
        }
    }

    // 如果都标记了，则返回n+1
    return n + 1;
}

3. 置换排序版本¶

C
/**
 * 置换排序版本 - 将每个正整数放到正确位置
 */
int firstMissingPositiveSwap(int A[], int n) {
    // 将每个正整数i放到A[i-1]的位置
    for (int i = 0; i < n; i++) {
        while (A[i] > 0 && A[i] <= n && A[A[i] - 1] != A[i]) {
            // 交换A[i]和A[A[i]-1]
            int temp = A[A[i] - 1];
            A[A[i] - 1] = A[i];
            A[i] = temp;
        }
    }

    // 查找第一个不在正确位置的数
    for (int i = 0; i < n; i++) {
        if (A[i] != i + 1) {
            return i + 1;
        }
    }

    return n + 1;
}

4. 算法正确性证明¶

定理：缺失的最小正整数在[1, n+1]范围内¶

证明： - 数组最多包含n个元素 - 最好的情况是包含1,2,3,...,n，此时答案为n+1 - 其他情况必然缺少某个[1,n]范围内的正整数 - 因此答案必定在[1, n+1]范围内

5. 边界情况处理¶

C
/**
 * 完善的边界处理版本
 */
int funcComplete(int A[], int n) {
    // 空数组情况
    if (n <= 0) return 1;

    // 分配内存并检查
    int *B = (int *)malloc(sizeof(int) * (n + 1));
    if (B == NULL) return -1;  // 内存分配失败

    // 初始化
    memset(B, 0, sizeof(int) * (n + 1));

    // 标记过程
    for (int i = 0; i < n; i++) {
        if (A[i] > 0 && A[i] <= n) {
            B[A[i]] = 1;
        }
    }

    // 查找过程
    for (int i = 1; i <= n; i++) {
        if (B[i] == 0) {
            free(B);
            return i;
        }
    }

    free(B);
    return n + 1;
}

6. 与其他解法的比较¶

方法	时间复杂度	空间复杂度	优缺点
哈希表法	O(n)	O(n)	简单直观，易理解
原地哈希	O(n)	O(1)	空间效率高，但实现复杂
置换排序	O(n)	O(1)	巧妙利用数组结构，但难理解
排序+遍历	O(n log n)	O(1)	简单但时间效率低

算法特点总结¶

高效性：时间复杂度O(n)，接近理论下界
正确性：基于严格的数学证明
实用性：适用于各种输入情况
可扩展性：可以扩展到其他相关问题
教育价值：体现了哈希表思想的经典应用

记忆要点¶

范围限定：答案必定在[1, n+1]范围内
哈希思想：用数组下标表示数值，值表示状态
三步法：
初始化标记数组
遍历标记出现的数
查找第一个未标记的数
边界处理：考虑空数组、全出现等情况
优化方向：可以进一步优化到空间O(1)