检查一个数组中的每个元素是否在第二个数组中

我有两个数组，我想检查arr2中的每个元素是否在arr1 。 如果元素的值在arr2重复，则需要在arr1中arr1相同的次数。 这样做的最好方法是什么？

 arr1 = [1, 2, 3, 4] arr2 = [1, 2] checkSuperbag(arr1, arr2) > true //both 1 and 2 are in arr1 arr1 = [1, 2, 3, 4] arr2 = [1, 2, 5] checkSuperbag(arr1, arr2) > false //5 is not in arr1 arr1 = [1, 2, 3] arr2 = [1, 2, 3, 3] checkSuperbag(arr1, arr2) > false //3 is not in arr1 twice 

Answer 1

一种select是对两个数组进行sorting，然后遍历这两个数组，比较元素。 如果在超级包中没有find子包候选中的元素，则前者不是子包。 sorting通常是O（n * log（n）），比较是O（max（s，t）），其中s和t是数组大小，总时间复杂度为O（m * log（m）） ，其中m = max（s，t）。

 function superbag(sup, sub) { sup.sort(); sub.sort(); var i, j; for (i=0,j=0; i<sup.length && j<sub.length;) { if (sup[i] < sub[j]) { ++i; } else if (sup[i] == sub[j]) { ++i; ++j; } else { // sub[j] not in sup, so sub not subbag return false; } } // make sure there are no elements left in sub return j == sub.length; } 

如果实际代码中的元素是整数，则可以使用专用的整数sortingalgorithm（例如基数sorting ）来计算总体O（max（s，t））时间复杂度，但是如果袋子很小， -in Array.sort运行速度可能比自定义的整数sorting要快。

时间复杂度较低的解决scheme是创build一个袋子types。 整数袋特别容易。 翻转袋子的现有数组：创build一个对象或一个整数作为键和数值重复计数的数组。 使用数组不会浪费空间，因为数组在Javascript中是稀疏的 。 您可以使用手提袋操作进行副袋或超级袋检查。 例如，从子候选中减去超级，并testing结果是否为空。 或者， contains操作应该是O（1）（或可能是O（log（n））），因此循环遍历候选子包并testing超级包容器是否超过每个子包的子包容器元素应该是O（n）或O（n * log（n））。

以下是未经testing的。 将isInt实现isInt练习。

 function IntBag(from) { if (from instanceof IntBag) { return from.clone(); } else if (from instanceof Array) { for (var i=0; i < from.length) { this.add(from[i]); } } else if (from) { for (p in from) { /* don't test from.hasOwnProperty(p); all that matters is that p and from[p] are ints */ if (isInt(p) && isInt(from[p])) { this.add(p, from[p]); } } } } IntBag.prototype=[]; IntBag.prototype.size=0; IntBag.prototype.clone = function() { var clone = new IntBag(); this.each(function(i, count) { clone.add(i, count); }); return clone; }; IntBag.prototype.contains = function(i) { if (i in this) { return this[i]; } return 0; }; IntBag.prototype.add = function(i, count) { if (!count) { count = 1; } if (i in this) { this[i] += count; } else { this[i] = count; } this.size += count; }; IntBag.prototype.remove = function(i, count) { if (! i in this) { return; } if (!count) { count = 1; } this[i] -= count; if (this[i] > 0) { // element is still in bag this.size -= count; } else { // remove element entirely this.size -= count + this[i]; delete this[i]; } }; IntBag.prototype.each = function(f) { var i; foreach (i in this) { f(i, this[i]); } }; IntBag.prototype.find = function(p) { var result = []; var i; foreach (i in this.elements) { if (p(i, this[i])) { return i; } } return null; }; IntBag.prototype.sub = function(other) { other.each(function(i, count) { this.remove(i, count); }); return this; }; IntBag.prototype.union = function(other) { var union = this.clone(); other.each(function(i, count) { if (union.contains(i) < count) { union.add(i, count - union.contains(i)); } }); return union; }; IntBag.prototype.intersect = function(other) { var intersection = new IntBag(); this.each(function (i, count) { if (other.contains(i)) { intersection.add(i, Math.min(count, other.contains(i))); } }); return intersection; }; IntBag.prototype.diff = function(other) { var mine = this.clone(); mine.sub(other); var others = other.clone(); others.sub(this); mine.union(others); return mine; }; IntBag.prototype.subbag = function(super) { return this.size <= super.size && null !== this.find( function (i, count) { return super.contains(i) < this.contains(i); })); }; 

另请参阅“ 比较JavaScript数组 ”，了解一组对象的示例实现，如果您不希望禁止重复使用元素。

Answer 2

你必须支持低俗的浏览器？ 如果没有， 每个function都应该使这个简单。

如果arr1是arr2的超集，那么arr2中的每个成员都必须存在于arr1中

 var isSuperset = arr2.every(function(val) { return arr1.indexOf(val) >= 0; }); 

这是一个小提琴

编辑

所以你定义的超集是这样的，对于arr2中的每个元素，它在arr1中出现的次数是相同的？ 我认为filter将帮助你做到这一点（从前面的MDN链接抓住垫片，以支持旧的浏览器）：

 var isSuperset = arr2.every(function (val) { var numIn1 = arr1.filter(function(el) { return el === val; }).length; var numIn2 = arr2.filter(function(el) { return el === val; }).length; return numIn1 === numIn2; }); 

更新小提琴

结束编辑

---

如果您确实想要支持较旧的浏览器，则上面的MDN链接有一个可以添加的填充程序，为了您的方便，我在此再现这些填充程序：

 if (!Array.prototype.every) { Array.prototype.every = function(fun /*, thisp */) { "use strict"; if (this == null) throw new TypeError(); var t = Object(this); var len = t.length >>> 0; if (typeof fun != "function") throw new TypeError(); var thisp = arguments[1]; for (var i = 0; i < len; i++) { if (i in t && !fun.call(thisp, t[i], i, t)) return false; } return true; }; } 

编辑

请注意，这将是O（N ² ）algorithm，所以请避免在大型数组上运行。

Answer 3

没有人发布recursion函数，而且总是很有趣。 把它arr1.containsArray( arr2 ) 。

演示： http : //jsfiddle.net/ThinkingStiff/X9jed/

 Array.prototype.containsArray = function ( array /*, index, last*/ ) { if( arguments[1] ) { var index = arguments[1], last = arguments[2]; } else { var index = 0, last = 0; this.sort(); array.sort(); }; return index == array.length || ( last = this.indexOf( array[index], last ) ) > -1 && this.containsArray( array, ++index, ++last ); }; 

Answer 4

使用对象（读取：散列表）而不是sorting应该将分摊的复杂度减less到O（m + n）：

 function bagContains(arr1, arr2) { var o = {} var result = true; // Count all the objects in container for(var i=0; i < arr1.length; i++) { if(!o[arr1[i]]) { o[arr1[i]] = 0; } o[arr1[i]]++; } // Subtract all the objects in containee // And exit early if possible for(var i=0; i < arr2.length; i++) { if(!o[arr2[i]]) { o[arr2[i]] = 0; } if(--o[arr2[i]] < 0) { result = false; break; } } return result; } console.log(bagContains([1, 2, 3, 4], [1, 3])); console.log(bagContains([1, 2, 3, 4], [1, 3, 3])); console.log(bagContains([1, 2, 3, 4], [1, 3, 7])); 

这产生true ， false ， false 。

Answer 5

至于另一种方法，你可以做如下：

 function checkIn(a,b){ return b.every(function(e){ return e === this.splice(this.indexOf(e),1)[0]; }, a.slice()); // a.slice() is the "this" in the every method } var arr1 = [1, 2, 3, 4], arr2 = [1, 2], arr3 = [1,2,3,3]; console.log(checkIn(arr1,arr2)); console.log(checkIn(arr1,arr3)); 

Answer 6

这里的快速解决scheme需要两个数组，如果b长于不能超级集合，则返回false。 然后通过b循环查看是否包含该元素。 如果是这样从a删除它，并继续如果不返回false。 更糟糕的情况是，如果b是一个子集，那么时间将b.length 。

 function isSuper(a,b){ var l=b.length,i=0,c; if(l>a.length){return false} else{ for(i;i<l;i++){ c=a.indexOf(b[i]); if(c>-1){ a.splice(c,1); } else{return false} } return true; } } 

这假设input不总是按顺序，如果a是1,2,3 ， b是3,2,1它仍然会返回true。

Answer 7

小版本：

 function checkSuperbag(arr1, arr2) { return !!~arr2.join('').indexOf(arr1.join('')) }