给定一个含 n(n≥1) 个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5, 3, 2, 3}中未出现的最小正整数是 1；数组{1, 2, 3}中未出现的最小正整数是 4。要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

(3) 说明你所设计算法的时间复杂度和空间复杂度。

顺序表

[tag_link]

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) {
  // 来记录 1 ~ n 是否出现过
  int vis[n];
  for (int i = 0; i < n; i++) {
    vis[i] = 0;
  }
  // 在 vis 数组中记录哪些正整数出现过
  for (int i = 0; i < n; i++) {
    int num = a[i];
    if (num > 0) {
      vis[num-1] = 1;
    }
  }
  // 遍历 vis 来找到最小消失的正整数
  for (int i = 0; i < n; i++) {
    if (vis[i] == 0) {
      return i+1;
    }
  }
  return n+1;
}

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