Array.filter的空间复杂度是多少？LeetCode数组找重复4种解法复杂度疑问

首先明确空间复杂度的计算规则：我们统计的是算法执行过程中额外申请的内存空间峰值，和变量引用的重新赋值无关，同时LeetCode默认规则下如果没有特殊说明，输出占用的空间也会纳入统计（题目明确说明输出不计入的情况除外）。

• 选项1：空间复杂度为 O(n)
  你的判断是正确的，result数组是独立申请的额外数组，最坏情况下长度可以达到n/2（比如数组是[1,1,2,2,3,3...]），属于线性级别的额外空间，不符合O(1)要求。
• 选项2：空间复杂度为 O(n)
  原生filter方法的底层实现就是生成一个全新的数组存储符合条件的元素，不管你之后是否把新数组赋值给原nums变量，执行filter的过程中已经申请了额外的O(n)空间，所以依然是线性空间复杂度。
• 选项3：空间复杂度为 O(n)
  和选项2没有本质区别，都是调用原生filter生成新数组，只是省略了赋值给nums变量的步骤，额外空间占用完全一致。
• 选项4：空间复杂度为 O(1)
  你的判断正确，filterInPlace是原地修改原数组，全程只用到了i、j两个临时变量，没有申请任何额外的数组空间，完全符合题目要求的O(1)空间限制。

补充说明 #

很多人会有“把新数组赋值给原变量就等于没有额外空间”的误区，这是不对的。空间复杂度统计的是执行过程中的内存峰值，你调用filter生成新数组的瞬间，内存里同时存在原数组和新数组两个O(n)级别的数组，所以峰值占用就是O(n)，和之后是否释放原数组的引用没有关系。
如果刷题时不想每次手写filterInPlace，也可以在第一次循环结束后，直接遍历数组把不符合条件的元素移到前面，最后截断数组返回，逻辑和filterInPlace完全一致，代码量也不大。

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