javascript - 根据另一个数组的内容过滤数组的最有效方法是什么？

Question

假设我有两个数组，items 和 removeItems，我希望从 items 中删除在 removeItems 中找到的任何值。

蛮力机制可能是:

var animals = ["cow","dog","frog","cat","whale","salmon","zebra","tuna"];
var nonMammals = ["salmon","frog","tuna","spider"];
var mammals = [];
var isMammal;

for(var i=0;i<animals.length;i++){
   isMammal = true;
   for(var j=0;j<nonMammals;j++){
     if(nonMammals[j] === animals[i]){
       isMammal = false;
       break;
     }
   }
   if(isMammal){
     mammals.push(animals[i]);
   }
}

这是什么？ O(N ^ 2)？有没有更有效的方法？

Answer 1

基本上你想要做的是有效地计算集合差异 S\T。我知道的(渐近)最快的方法是将 T 放入 HashMap 中(这使得 |T| 步骤)并遍历 S 中的每个 s(这使得 |S| 步骤)检查 T 中是否存在 s(这是 O(1))。所以你得到了 O(|T| + |S|) 步。