用于从数组中删除项目的有效算法

Question

我正在寻找一种高效的 JavaScript 实用程序方法，该方法在 O(n) 中将在适当的位置从数组中删除一组项目。您可以假设与 === 运算符相等会正常工作。

这是一个示例签名（为了类型清晰，用 TypeScript 编写）

function deleteItemsFromArray<T>(array: T[], itemsToDelete: T[]) { ... }

我的想法是分两次完成。第一遍获取需要删除的索引。然后第二遍通过从被删除的当前索引到被删除的下一个索引向后复制来压缩数组。

有没有人有这样的代码已经很方便或更有效的方法来做到这一点？

PS请不要filter指出创建数组副本的函数，它不起作用。

Answer 1

遍历数组，将不在数组中的元素复制到数组中itemsToDelete的下一个目标索引。删除元素时，不会增加此索引。

最后，在末尾重置数组的长度以去除末尾剩余的元素。

function deleteItemsFromArray(array, itemsToDelete) {
  let destIndex = 0;
  array.forEach(e => {
    if (!itemsToDelete.includes(e)) {
      array[destIndex++] = e;
    }
  });
  array.length = destIndex;
}

const array = [1, 2, 3, 4, 5, 6, 7];
deleteItemsFromArray(array, [3, 5]);
console.log(array);