javascript - 如何提高 javascript 数组操作中嵌套循环的性能？

Question

我做了一个编码挑战，要求通过仅添加一次重复元素并保持数组元素的顺序，将数组输入合并到新数组中。我的解决方案如下:

function union(arr){
 let newArr = [];
 let length = arr.length;
 for(let i=0; i< length; i++){
   for(let j=0; j<arr[i].length; j++){
   if(!newArr.includes(arr[i][j])){
     newArr.push(arr[i][j]);
   }
  }
 }
 return newArr;

我想知道如何在不使用任何 javascript 内置方法(如reduce 或map 等)的情况下提高上述解决方案的大O 性能。有没有一种不使用嵌套循环的方法？

Answer 1

如果允许的话，我建议将所有数组添加到集合中(重复的项目将被忽略)，然后将集合重新转换为数组:

function union(input){
  const set = new Set(input.flat());
  return [...set];
}

console.log(union([[2, 3], [3, 4]]));

如果计算复杂性是一个问题，那么使用集合而不是数组通常是个好主意 - Array.prototype.includes 是 O(N)，例如，而Set.prototype.has是O(1)。