我有两个数组，我想检查中的每个元素是否都arr2在arr1. 如果一个元素的值在 中重复arr2，则需要重复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
你必须支持糟糕的浏览器吗？如果没有，every函数应该使这变得容易。
如果 arr1 是 arr2 的超集，则 arr2 中的每个成员都必须存在于 arr1 中
var isSuperset = arr2.every(function(val) { return arr1.indexOf(val) >= 0; });
这是一把小提琴
编辑
所以你定义的超集对于 arr2 中的每个元素，它在 arr1 中出现的次数相同？我认为过滤器会帮助你做到这一点（从前面的 MDN 链接中获取 shim 以支持旧浏览器）：
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 2 ) 算法，因此请避免在大型数组上运行它。
一种选择是对两个数组进行排序，然后遍历两者，比较元素。如果在超级包中没有找到子包候选中的元素，则前者不是子包。排序一般为 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;
}
如果实际代码中的元素是整数，则可以使用特殊用途的整数排序算法（例如radix sort）来实现整体 O(max(s,t)) 时间复杂度，但如果包很小，则构建的-inArray.sort可能比自定义整数排序运行得更快。
时间复杂度可能较低的解决方案是创建包类型。整数袋特别容易。翻转包的现有数组：创建一个对象或数组，以整数为键，重复计数值。使用数组不会浪费空间，因为数组在 Javascript 中是稀疏的。您可以使用包操作进行子包或超级包检查。例如，从子候选中减去 super 并测试结果是否为非空。或者，contains操作应该是 O(1)（或可能是 O(log(n))），因此循环遍历候选子袋并测试超级袋的容纳量是否超过每个子袋元素的子袋的容纳量应该是 O(n) 或 O(n*log(n))。
以下内容未经测试。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 数组”以获取一组对象的示例实现。
还没有人发布过递归函数，这些函数总是很有趣。称之为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 );
};
在github lodash库上找到了这个。该函数使用内置函数来解决问题。.includes()，.indexOf()和.every()
var array1 = ['A', 'B', 'C', 'D', 'E'];
var array2 = ['B', 'C', 'E'];
var array3 = ['B', 'C', 'Z'];
var array4 = [];
function arrayContainsArray (superset, subset) {
if (0 === subset.length) {
return false;
}
return subset.every(function (value) {
return (superset.includes(value));
});
}
function arrayContainsArray1 (superset, subset) {
if (0 === subset.length) {
return false;
}
return subset.every(function (value) {
return (superset.indexOf(value) >= 0);
});
}
console.log(arrayContainsArray(array1,array2)); //true
console.log(arrayContainsArray(array1,array3)); //false
console.log(arrayContainsArray(array1,array4)); //false
console.log(arrayContainsArray1(array1,array2)); //true
console.log(arrayContainsArray1(array1,array3)); //false
console.log(arrayContainsArray1(array1,array4)); //false使用对象（读取：哈希表）代替排序应该将摊销复杂度降低到 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。