JS调用sort()查找缺失自然数能否满足O(n)时间复杂度要求

最终结论 #

这个实现方案的时间复杂度肯定超过O(n)，完全不符合题目要求。

原因说明 #

• 拖慢复杂度的核心是开头的arr.sort()调用：ECMAScript标准没强制要求sort的实现算法，但现在所有主流JS引擎用的排序算法，时间复杂度最低都是O(nlogn)（比如V8引擎对长度超过22的数组用Timsort），短数组场景用的插入排序最坏复杂度甚至到O(n²)，不管哪种都比要求的线性复杂度O(n)高一个量级以上。
• 算法整体时间复杂度取耗时最高的步骤的阶，就算后面的for循环是O(n)，整体复杂度还是排序带来的O(nlogn)，根本达不到O(n)的要求。
• 额外说一句，这个写法连正确性都有问题：直接调用无参sort()的时候，JS会把所有元素转成字符串按Unicode码点排序，根本不是按数值大小排，比如数组[10, 2]排序后结果是[10, 2]，后续遍历比对的时候直接就会判错结果。

符合O(n)要求的正确实现思路 #

根本不需要排序，两种常见的线性时间方案就能搞定：

• 求和法：0到n的自然数总和可以直接用公式n*(n+1)/2算出来（这里n就是数组长度，因为缺了一个数，完整序列长度是n+1，最大值是n），用这个总和减去数组里所有元素的和，剩下的差值就是缺失的数。示例代码：

function findMissed(arr) {
  const n = arr.length;
  let sum = n * (n + 1) / 2;
  for (const num of arr) {
    sum -= num;
  }
  return sum;
}

• 异或法：利用异或运算「两个相同的数异或结果为0、0和任何数异或都是数本身」的特性，把0到n的所有数，和数组里的所有数依次做异或，最后剩下的结果就是只出现了一次的缺失值，这个方法还能避免求和时数字太大溢出的问题。示例代码：

function findMissed(arr) {
  let res = arr.length;
  for (let i = 0; i < arr.length; i++) {
    res ^= i ^ arr[i];
  }
  return res;
}

这两种写法都只需要遍历一次数组，没有排序、没有嵌套循环，时间复杂度稳定O(n)，额外空间只有几个变量，空间复杂度O(1)，完全满足题目要求。

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