Array.filter 的 Space 复杂度是多少？

Question

我刚刚完成了 Leetcode 问题 Find All Duplicates in an Array 并且对问题的 space 复杂性有一些疑问。这个问题特别要求 O(1) space 复杂度。下面我写了四种不同的方法来解决这个问题，但我不确定每个选项的 space 复杂度是多少。

我想到的四个选项是：

创建一个结果数组并在其中存储重复的数字。然后return这个数组。我相信这是 O(n) 因为我需要额外的数组。
过滤 nums 数组并将其存储在 nums 变量中。我不确定这是 O(1) 还是 O(n)，因为我现在正在生成一个新数组，但会立即替换我的原始数组。
过滤 nums 数组并立即 return 新数组。
使用自定义的 filterInPlace 函数修改 nums 数组的大小。我相信这是 O(1)，但需要为 Leetcode 问题编写代码有点麻烦。

我希望对此有所澄清。谢谢！

const findDuplicates = (nums) => {
  
  const swap = (i, j) => {
    [nums[i], nums[j]] = [nums[j], nums[i]];
  };
  
  let i = 0;
  let idx;
  const n = nums.length;
  
  while (i < n) {
    
    idx = nums[i] - 1;
    
    if (nums[i] !== nums[idx]) {
      swap(i, idx);
    } else {
      i += 1;
    }
  }
  
  // Option 1 - Use a results array to contain duplicates
  const result = [];
  for (let i = 0; i < n; i += 1) {
    if (nums[i] !== i + 1) {
      result.push(nums[i]);
    }
  }
  return result;

  // Option 2 - Filter out duplicates and save in nums, then return nums
  nums = nums.filter((num, i) => num !== i + 1);
  return nums;

  // Option 3 - Return the new array returned from Array.filter
  return nums.filter((num, i) => num !== i + 1);

  // Option 4 - Write a filterInPlace function to modify array in place
  const filterInPlace = (array, condition) => {

    // The number of items that have been kept
    let j = 0;
    
    for (let i = 0; i < array.length; i += 1) {
      if (condition(array[i], i)) {
        array[j] = array[i];
        j += 1;
      }
    }
   
    array.length = j;
    return array;
  }

  filterInPlace(nums, (num, i) => num !== i + 1);
  return nums;

}

Answer 1

space肯定会O(n)。
和3.两者是一样的，可以直接return它或者赋值给新的变量，然后return它。 Array.filter return 一个新的必需元素数组，也是 O(n) space 新形成的数组。

这是O(1)因为你只是修改了nums数组

Array.filter 的 Space 复杂度是多少？

What is the Space Complexity of Array.filter?

javascript

arrays

space-complexity