排查Codility平台上失败的数组缺失最小正整数求解代码问题

背景 #

已知该问题已有相关提问，本次旨在定位个人解决方案失效的原因。Codility平台无法查看完整测试用例，自行测试的大部分用例均能通过，但仍有1/4测试用例未通过，且性能得分为0。

问题描述 #

编写函数，给定由N个整数组成的数组A，返回数组中未出现的最小正整数（大于0）。

示例 #

• 给定A = [1, 3, 6, 4, 1, 2]，函数应返回5。
• 给定A = [1, 2, 3]，函数应返回4。
• 给定A = [−1, −3]，函数应返回1。
• 给定A = [2, 2, 2]，函数应返回1。

我的解决方案 #

function solution(A) {
  const positivesOfA = A.filter(elem => elem > 0);
  const limit = Math.max(...A);
  let res = [];

  if (positivesOfA.length == 0) {
    return 1;
  } else {
    for (var i = 1; i <= limit; i++) {
      if (!A.includes(i)) {
        res.push(i);
      }
    }
    return (res.length == 0 ? limit + 1 : Math.min(...res))
  }
}

代码存在的问题 #

1. 严重的性能问题（导致性能得分为0） #

• 时间复杂度极高：A.includes(i)是O(n)的操作，而循环会从1执行到Math.max(...A)。如果数组中存在极大的正整数（比如1e9），循环会执行1e9次，直接导致超时；即使数组最大元素是1e5，总时间复杂度也会达到O(n²)，完全无法通过Codility的大测试用例。
• Math.max(...A)的潜在栈溢出：当数组A的元素数量过多（比如超过10万），使用扩展运算符...传递参数会超出JS函数的参数长度限制，引发栈溢出错误，导致代码崩溃。

2. 逻辑漏洞（导致部分测试用例失败） #

虽然常规测试用例能通过，但当数组包含极大值时，循环无法在合理时间内完成，直接导致这类测试用例判定失败，这就是你看到1/4测试用例未通过的核心原因之一。

优化方向提示 #

• 可以利用数组下标作为哈希表，将数组中1~N范围内的数放到对应下标的位置，之后遍历数组找到第一个下标与数值不匹配的位置，即为缺失的最小正整数；如果全部匹配则返回N+1。这种方法时间复杂度为O(n)，空间复杂度为O(1)（原地修改数组）。
• 也可以使用Set存储数组中的正整数，然后从1开始遍历，找到第一个不在Set中的数，这种方法时间复杂度O(n)，空间复杂度O(n)，实现更简单。

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