基于另一个数组的内容过滤数组的最有效方法是什么？

Question

假设我有两个数组,items和removeItems,我希望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放入一个散列图(这使得| T |步骤)并将每个s放在S中(这使得| S |步骤)检查T中的数据(即O(1)).所以你得到O(| T | + | S |)步骤.

Answer 2

那是实际的O(M * N).

可能你最好animals先对数组进行排序,然后进行二分查找.你可以减少到O(N * log N)- 好吧,log N < M不管怎么说.

无论如何,如果你与JS的工作和运行客户端,那么就尽量保持数据量最小,或者他们的浏览器会骂你的每个请求.