Javascript 检查一个数组中的每个元素是否都在第二个数组中
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/8628059/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Check if every element in one array is in a second array
提问by Harry
I have two arrays and I want to check if every element in arr2is in arr1. If the value of an element is repeated in arr2, it needs to be in arr1an equal number of times. What's the best way of doing this?
我有两个数组，我想检查中的每个元素是否都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
采纳答案by outis
One option is to sort the two arrays, then traverse both, comparing elements. If an element in the sub-bag candidate is not found in the super-bag, the former is not a sub-bag. Sorting is generally O(n*log(n)) and the comparison is O(max(s,t)), where sand tare the array sizes, for a total time complexity of O(m*log(m)), where m=max(s,t).
一种选择是对两个数组进行排序，然后遍历两者，比较元素。如果在超级包中没有找到子包候选中的元素，则前者不是子包。排序一般为 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;
}
If the elements in the actual code are integers, you can use a special-purpose integer sorting algorithm (such as radix sort) for an overall O(max(s,t)) time complexity, though if the bags are small, the built-in Array.sortwill likely run faster than a custom integer sort.
如果实际代码中的元素是整数，则可以使用特殊用途的整数排序算法（例如radix sort）来实现整体 O(max(s,t)) 时间复杂度，但如果包很小，则构建的-inArray.sort可能比自定义整数排序运行得更快。
A solution with potentially lesser time-complexity is to create a bag type. Integer bags are particularly easy. Flip the existing arrays for the bags: create an object or an array with the integers as keys and a repeat count for values. Using an array won't waste space by creating as arrays are sparse in Javascript. You can use bag operations for sub-bag or super-bag checks. For example, subtract the super from the sub candidate and test if the result non-empty. Alternatively, the containsoperation should be O(1) (or possibly O(log(n))), so looping over the sub-bag candidate and testing if the super-bag containment exceeds the sub-bag's containment for each sub-bag element should be O(n) or O(n*log(n)).
时间复杂度可能较低的解决方案是创建包类型。整数袋特别容易。翻转包的现有数组：创建一个对象或数组，以整数为键，重复计数值。使用数组不会浪费空间，因为数组在 Javascript 中是稀疏的。您可以使用包操作进行子包或超级包检查。例如，从子候选中减去 super 并测试结果是否为非空。或者，contains操作应该是 O(1)（或可能是 O(log(n))），因此循环遍历候选子袋并测试超级袋的容纳量是否超过每个子袋元素的子袋的容纳量应该是 O(n) 或 O(n*log(n))。
The following is untested. Implementation of isIntleft as an exercise.
以下内容未经测试。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);
}));
};
See also "comparing javascript arrays" for an example implementation of a set of objects, should you ever wish to disallow repetition of elements.
如果您希望禁止重复元素，请参阅“比较 javascript 数组”以获取一组对象的示例实现。
回答by Adam Rackis
Do you have to support crummy browsers? If not, the everyfunction should make this easy.
你必须支持糟糕的浏览器吗？如果没有，every函数应该使这变得容易。
If arr1 is a superset of arr2, then each member in arr2 must be present in arr1
如果 arr1 是 arr2 的超集，则 arr2 中的每个成员都必须存在于 arr1 中
var isSuperset = arr2.every(function(val) { return arr1.indexOf(val) >= 0; });
Here's a fiddle
这是一把小提琴
EDIT
编辑
So you're defining superset such that for each element in arr2, it occurs in arr1 the same number of times? I think filterwill help you do that (grab the shim from the preceding MDN link to support older browsers):
所以你定义的超集对于 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;
});
END EDIT
结束编辑
If you do want to support older browsers, the MDN link above has a shim you can add, which I reproduce here for your convenience:
如果你确实想支持旧浏览器，上面的 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;
};
}
EDIT
编辑
Note that this will be an O(N2) algorithm, so avoid running it on large arrays.
请注意，这将是一个 O(N 2) 算法，因此请避免在大型数组上运行它。
回答by ThinkingStiff
No one has posted a recursive function yet and those are always fun. Call it like arr1.containsArray( arr2 ).
还没有人发布过递归函数，这些函数总是很有趣。称之为arr1.containsArray( arr2 ).
Demo: http://jsfiddle.net/ThinkingStiff/X9jed/
演示：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 );
};
回答by Ashish Singh Rawat
Found this on github lodashlibrary. This function use built in functions to solve the problem. .includes(), .indexOf()and .every()
在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回答by mzedeler
Using objects (read: hash tables) in stead of sorting should reduce the amortized complexity to O(m+n):
使用对象（读取：哈希表）代替排序应该将摊销复杂度降低到 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]));
Which yields true, false, false.
其中产生true, false, false。
回答by SuperNova
If arr2 is subset of arr1, then Length of set(arr1 + arr2) == Length of set(arr1)
如果 arr2 是 arr1 的子集，则 Length of set(arr1 + arr2) == Length of set(arr1)
var arr1 = [1, 'a', 2, 'b', 3];
var arr2 = [1, 2, 3];
Array.from(new Set(arr1)).length == Array.from(new Set(arr1.concat(arr2))).length
回答by Cholakov
Here is my solution:
这是我的解决方案：
Array.prototype.containsIds = function (arr_ids) {
var status = true;
var current_arr = this;
arr_ids.forEach(function(id) {
if(!current_arr.includes(parseInt(id))){
status = false;
return false; // exit forEach
}
});
return status;
};
// Examples
[1,2,3].containsIds([1]); // true
[1,2,3].containsIds([2,3]); // true
[1,2,3].containsIds([3,4]); // false
回答by Redu
As for another approach you may do as follows;
至于另一种方法，您可以执行以下操作；
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));回答by qw3n
Quick solution here take two arrays if bis longer than it can't be a super set so return false. Then loop through bto see if a contains the element. If so delete it from aand move on if not return false. Worse case scenario is if bis a subset then time will b.length.
这里的快速解决方案需要两个数组，如果b长于它不能是一个超级集，所以返回 false。然后循环b查看 a 是否包含该元素。如果是这样，将其删除a并继续，如果不返回 false。更糟糕的情况是 ifb是一个子集，那么 time will 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;
}
}
This assumes that inputs will not always be in order and if ais 1,2,3and bis 3,2,1it will still return true.
这假设输入并不总是按顺序排列，如果a是1,2,3和b是，3,2,1它仍然会返回 true。
