基于另一个数组的内容过滤数组的最有效方法是什么?
-
03-07-2019 - |
题
假设我有两个数组,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)?有更有效的方法吗? 解决方案
实际上是O(M * N)
。
可能你最好先对animals
数组进行排序,然后进行二进制搜索。你将能够减少到O(N * log N)
- 好吧,无论如何log N < M
。
无论如何,如果您正在使用JS并且运行客户端,那么只需尽量减少数据量,否则他们的浏览器会在每次请求时对您大喊大叫。
不隶属于 StackOverflow