防止循环中的循环。如何降低复杂性

Question

你有 2 个数组。
arrA 是空的。
arrB 充满了东西（它充满了什么并不重要，但假设它很大）。

当用户做某事时，一个项目从 arrB 中删除，该项目被放置在 arrA 中。

当用户做不同的事情时，它从 arrA 中提取项目并将其放入 arrB 中。

是否可以在没有循环内循环的情况下执行此操作？

或者用计算机科学术语来说：
是否可以用线性 ( ϴ(n) ) time/space 复杂度来做到这一点？
现在我有至少 ϴ(n*k)

（其中 n 是 arrB 的长度，k 是传递给 applyItems 的项目数）：

var arrA = [], arrB = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0];

function addToArray(arrayToAddTo, item){
  if(arrayToAddTo.indexOf(item) === -1){
    arrayToAddTo.push(item);
  }
}

function removeFromArray(arrayToRemoveFrom, item){
  var i = arrayToRemoveFrom.length;
  var temp = [];
  while(i--){
    if(arrayToRemoveFrom[i] !== item){
      temp.push(arrayToRemoveFrom[i]);
    }   
  }
  return temp;
}

function applyItems(arrayOfItems){
  var i = arrayOfItems.length;
  while(i--){
    var current = arrayOfItems[i]
    addToArray(arrA, current);
    arrB = removeFromArray(arrB, current);
  }
}

applyItems([0, 5, 3]);
console.log(arrA);
console.log(arrB);

applyItems 有效，但效率不高。

这里可以降低 time/space 的复杂性吗？

Answer 1

是的。您可以使用 splice().

而不是创建自己的删除函数

因此，您可以 arrB.splice(i, 1); 而不是 removeFromArray(arrB, current)。这将从索引 i.

中删除 1 元素

您不需要遍历每个元素来检查它是否与您想要的匹配 - 只需使用 indexOf()。所以你可以做类似

的事情

 var i = arrA.indexOf(item)

Answer 2

根据我的评论：

You can use native tools that will be way faster than manually looping. removeFromArray can use indexOf to get the position of the one to remove and then uses splice to remove it. Also you can work with reference instead of recreating the array every time.

还有一些其他优化...

var arrA = [], arrB = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0];

function addToArray(item){
  if(arrA.indexOf(item) === -1){
    arrA.push(item);
  }
}

function removeFromArray(item){
  var index = arrB.indexOf(item);
  if (index > -1) {
    arrB.splice(index, 1);
  }
}

function applyItems(arrayOfItems){
  arrayOfItems.map(function(item) {
      addToArray(item);
      removeFromArray(item);
  });
}

applyItems([0, 5, 3]);
console.log(arrA);
console.log(arrB);

Answer 3

Right now I have something that is at least ϴ(n*k)

您可以 O(n+k) 通过对 arrayOfItems 使用不需要循环的高效查找结构，但允许您在 O(1) 中确定是否应将某个项目换成另一个数组。这样，单次通过 arrB 就足够了。
或者，如果您对数组进行排序并使用二进制搜索进行查找，您将得到 O(log k * (n+k))。但是，如果您的数组是有限的并且无论如何都非常小，那无关紧要。

此外，您应该在 addToArray 中省略 indexOf 测试。似乎已经确定 arrA 和 arrB 中都没有任何项目（并且您的算法保持不变），因此您不必在将项目推送到数组之前检查重复项。

防止循环中的循环。如何降低复杂性

Preventing a loop within a loop. How to reduce complexity

javascript

arrays

performance

time-complexity

space-complexity