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

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

实际上是O(M * N)。

可能你最好先对animals数组进行排序，然后进行二进制搜索。你将能够减少到O(N * log N) - 好吧，无论如何log N < M。

无论如何，如果您正在使用JS并且运行客户端，那么只需尽量减少数据量，否则他们的浏览器会在每次请求时对您大喊大叫。

Answer 2

基本上你想要做的是有效地计算集合差值S \ T.我知道的（渐近）最快的方法是将T放入一个散列图（这使得| T |步骤）并在S中遍历每个s（这使得| S |步骤）检查T（即O（1））。所以你得到了O（| T | + | S |）步骤。

Answer 3

使用jQuery非常简单：

function is_mammal(animal)
{
    return $.inArray(animal, nonMammals) == -1;
}

mammals = $.grep(animals, is_mammal);

请参阅 $.grep 和 $.inArray 。