从阵列中删除项目的高效算法 [英] Efficient algorithm for removing items from an array in place

问题描述

我正在寻找一种有效的JavaScript实用程序方法，该方法可以在O(n)中从数组就地中删除一组项目.您可以假定与===运算符相等将正常工作.

I'm looking for an efficient JavaScript utility method that in O(n) will remove a set of items from an array in place. You can assume equality with the === operator will work correctly.

这是示例签名(为清晰起见，使用TypeScript编写)

Here is an example signature (written in TypeScript for type clarity)

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

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

My thought is to do this in two passes. The first pass gets the indexes that need to be removed. The second pass then compacts the array by copying backwards from the current index being removed through the next index being removed.

有人有这样的代码已经很方便或更有效的方法吗?

Does anyone have code like this already handy or a more efficient way to do this?

P.S.请不要指出 filter 函数，因为它会创建数组的副本，因此无法正常工作.

P.S. Please don't point out the filter function as that creates a copy of the array, it does not work in place.

推荐答案

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

Iterate over the array, copying elements that aren't in itemsToDelete to the next destination index in the array. When you delete an element, you don't increment this index.

最后，在最后重置数组的长度，以消除最后的其余元素.

Finally, reset the length of the array at the end to get rid of the remaining elements at the end.

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);

这篇关于从阵列中删除项目的高效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！