代码之家 › 专栏 › 技术社区 › Bjorn

根据另一个数组的内容筛选数组的最有效方法是什么?

filtering arrays javascript

1

Bjorn · 技术社区 · 17 年前

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

蛮力机制可能是:

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)?有没有更有效的方法?

3 回复 | 直到 17 年前

1

6

bayer 17 年前

基本上,你要做的是有效地计算集差S\T。我知道的(渐进)最快的方法是将T放入哈希映射(产生| T |步数)中,然后在S中遍历每个S(产生| S |步数),检查T中的S(即O(1))。所以你可以走O(| T |+| S |)步。

2

5

Seb 17 年前

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

也许你可以做得更好的分类 animals 数组,然后进行二进制搜索。你可以减少到 O(N * log N) -好吧,如果 log N < M

无论如何,如果您使用的是JS,并且它运行客户端,那么请尽量将数据量保持在最低限度,否则他们的浏览器会在每次请求时对您大喊大叫。

3

2

tghw megawac 17 年前

使用jQuery非常简单:

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

mammals = $.grep(animals, is_mammal);

$.grep 和 $.inArray .