1

假设我有两个数组，items 和 removeItems，我希望从 item 中删除 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)? 有没有更有效的方法？

4

3 回答 3

6

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

于 2009-04-28T22:56:35.023 回答
5

原来如此O(M * N)。

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

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

于 2009-04-28T22:43:28.690 回答
2

使用 jQuery 非常简单：

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

mammals = $.grep(animals, is_mammal);

请参阅$.grep和的文档$.inArray。

于 2009-04-28T22:47:56.900 回答