Array.filter的空间复杂度是多少?

Question

我刚刚完成了Leetcode问题查找数组中的所有重复项，并对该问题的空间复杂性有一些疑问。这个问题特别要求空间复杂度为0(1)。下面我写了四种不同的方法来解决这个问题，但我不确定这些选项的空间复杂度是多少。

我想到的四个选项是:

1. 创建一个结果数组并在其中存储重复的数字。然后返回这个数组。我认为这是O(n)，因为我需要额外的数组。
2. 筛选nums数组并将其存储在nums变量中。我不确定这是O(1)还是O(n)，因为我现在正在生成一个新数组，但随后立即替换原来的数组。
3. 过滤nums数组并立即返回新数组
4. 使用自定义filterInPlace函数来修改nums数组的大小。我相信这是0(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

1. 空格肯定是O(n)

2. 3。两者都是一样的，你可以直接返回它或赋值给新变量，然后返回它。数组中。filter返回一个包含所需元素的新数组，该数组也是新形成的数组的O(n)空间。

4. 这是O(1)，因为你刚刚修改了nums数组