题13

题13

题目

【2018 统考真题】给定一个含 个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组 中未出现的最小正整数是 1 ; 数组 中未出现的最小正整数是 4 。要求:

1. 给出算法的基本设计思想。
2. 根据设计思想, 采用 C 或 C++语言描述算法, 关键之处给出注释。
3. 说明你所设计算法的时间复杂度和空间复杂度。

分析

解

1. 算法的基本设计思想:

要求在时间上尽可能高效,因此采用空间换时间的办法。分配一个用于标记的数组 B[n] ,用来记录 A 中是否出现了 1 ~ n 中的正整数, B[0] 对应正整数 1,B[n - 1] 对应正整数 n ,初始化 B 中全部为 0 。由于 A 中含有 n 个整数,因此可能返回的值是 1 ~ n + 1 ,当 A 中 n 个数恰好为 1 ~ n 时返回 n + 1 。当数组 A 中出现了小于或等于 0 或大于 n 的值时,会导致 1 ~ n 中出现空余位置,返回结果必然在 1 ~ n 中,因此对于 A 中出现了小于或等于 0 或大于 n 的值,可以不采取任何操作。

经过以上分析可以得出算法流程: 从 A[0] 开始遍历 A ,若 0 < A[i] <= n ,则令 B[A[i] - 1] = 1 ; 否则不做操作。对 A 遍历结束后,开始遍历数组 B ,若能查找到第一个满足 B[i] == 0 的下标 i , 返回 i + 1 即为结果,此时说明 A 中未出现的最小正整数在 1 和 n 之间。若 B[i] 全部不为 0 ,返回 i + 1 (跳出循环时 i = n, i + 1 等于 n + 1 ),此时说明 A 中未出现的最小正整数是 n + 1 。

2. 算法实现:

int findMissMin(int A[], int n) {
    int *B; // 标记数组
    B = ( int * )malloc(sizeof(int) * n); // 分配空间
    memset(B, 0, sizeof(int) * n); // 赋初值为 0
 
    for (int i = 0; i < n; i++) {
        if (A[i] > 0 && A[i] <= n) // 若 A[i] 的值介于 1 ~ n ,则标记数组 B
            B[A[i] - 1] = 1;
    }
 
    for (int i = 0; i < n; i++) // 扫描数组 B ,找到目标值
        if (B[i] == 0) break;
 
    return i + 1; // 返回结果
}

3. 时间复杂度: 遍历 A 一次,遍历 B 一次,两次循环内操作步骤为 O(1) 量级,因此时间复杂度为 O(n) 。空间复杂度: 额外分配了 B[n] ,空间复杂度为 O(n) 。