检查，如果在一个阵列的每个元素是在第二阵列 [英] Check if every element in one array is in a second array
问题描述
我有两个数组，我想检查 ARR2 的每一个元素是 ARR1 。如果 ARR2 重复元素的值，就需要在 ARR1 相同的次数。什么是这样做的最佳方式？
ARR1 = [1，2，3，4]
ARR2 = [1，2]checkSuperbag（ARR1，ARR2）
＆GT;真//既1和2是在ARR1ARR1 = [1，2，3，4]
ARR2 = [1，2,5]checkSuperbag（ARR1，ARR2）
＆GT;假// 5不ARR1ARR1 = [1，2，3]
ARR2 = [1，2，3，3]checkSuperbag（ARR1，ARR2）
＆GT;假// 3不在ARR1两次
一个选项是两个数组排序，然后遍历两者比较的元素。如果在超袋没有发现在副袋候补的要素，前者是不是一个子包。排序一般为O（n *的log（n））和比较是O（MAX（S，T）），其中的取值的和的 T 的是数组大小，为的O的总时间复杂度（M *日志（米）），其中m = MAX（S，T）。
函数superbag（SUP，分）{
sup.sort（）;
sub.sort（）;
变种I，J;
对于（I = 0，J = 0; I＆下; sup.length＆放大器;＆放大器; J＆下; sub.length）{
如果（SUP [1] - ;分[J]）{
++我;
}否则如果（SUP [I] ==子[J]）{
++我; ++焦耳;
}其他{
//子[J]不是在燮，所以没有分subbag
返回false;
}
}
//确保有没有留在子元素
复位J == sub.length;
}
如果在实际的code中的元素都是整数，你可以使用一个专用的整数排序算法（如基数排序）全面O（MAX（S，T））的时间复杂度，但如果包装袋小，内置的中的Array.sort 将有可能跑得比一个自定义排序整数更快。
与潜在的较小的时间复杂度的解决方案是创建一个包类型。整袋是特别容易。翻转现有阵列的袋子：创建一个对象或与整数作为键和值重复计数的数组。使用数组作为阵列在Javascript 稀疏不会通过创建浪费空间。您可以使用包业务进行分袋或超袋检查。例如，减去分考生和测试，如果结果非空超。另外，包含操作应该是O（1）（也可能是O（日志（N））），所以遍历子包候选人和测试，如果超包围堵超过了包包子的每个子包元素遏制应该是O（N）或O（N *的log（n））。
以下是未经测试。 isInt 的实施留下作为一个练习。
函数IntBag（从）{
如果（从的instanceof IntBag）{
返回from.clone（）;
}否则如果（从阵列的instanceof）{
对于（VAR I = 0; I＆LT; from.length）{
this.add（从[I]）;
}
}否则如果（从）{
对于（从P）{
/ *不测试from.hasOwnProperty（P）;所有事项
是，p和从[P]是整数
* /
如果（isInt（对）及＆放大器; isInt（从[P]））{
this.add（对，从[P]）;
}
}
}
}
IntBag.prototype = [];
IntBag.prototype.size = 0;
IntBag.prototype.clone =功能（）{
VAR克隆=新IntBag（）;
this.each（函数（I，计数）{
clone.add（I，计数）;
}）;
返回的克隆;
};
IntBag.prototype.contains =函数（ⅰ）{
如果（在此我）{
返回此[I]
}
返回0;
};
IntBag.prototype.add =功能（我，算）{
如果（！计数）{
数= 1;
}
如果（在此我）{
这[一] + =计数;
}其他{
这个由[i] =计数;
}
this.size + =计数;
};
IntBag.prototype.remove =功能（I，计数）{
如果（！我在这个）{
返回;
}
如果（！计数）{
数= 1;
}
这[一] - =计数;
如果（在此由[i]＆0）{
//元素仍然在包
this.size - =计数;
}其他{
//完全删除元素
this.size - =计数+这[一]
删除[I]
}
};
IntBag.prototype.each =函数（f）{
VAR我;
的foreach（在此我）{
F（I，这[一]）;
}
};
IntBag.prototype.find =功能（P）{
VAR的结果= [];
VAR我;
的foreach（我this.elements）{
如果（P（I，这由[i]））{
返回我;
}
}
返回null;
};
IntBag.prototype.sub =功能（其他）{
other.each（函数（I，计数）{
this.remove（I，计数）;
}）;
返回此;
};
IntBag.prototype.union =功能（其他）{
VAR工会= this.clone（）;
other.each（函数（I，计数）{
如果（union.contains（I）所述;计数）{
union.add（I，计数 - union.contains（I））;
}
}）;
返回工会;
};
IntBag.prototype.intersect =功能（其他）{
VAR路口=新IntBag（）;
this.each（函数（I，计数）{
如果（other.contains（ⅰ））{
intersection.add（I，Math.min（计数，other.contains（I）））;
}
}）;
返回路口;
};
IntBag.prototype.diff =功能（其他）{
变种矿= this.clone（）;
mine.sub（其他）;
变种更为= other.clone（）;
others.sub（本）;
mine.union（他人）;
回到我的。
};
IntBag.prototype.subbag =功能（超）{
返回this.size＆LT; = super.size
＆功放;＆安培;空！== this.find（
功能（我，算）{
返回super.contains（I）所述; this.contains（ⅰ）;
}））;
};
另请参阅比较JavaScript数组的一个示例实现一组对象的，你曾经想禁止元素的重复。
I have two arrays and I want to check if every element in arr2 is in arr1. If the value of an element is repeated in arr2, it needs to be in arr1 an equal number of times. What's the best way of doing this?
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
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 s and t are the array sizes, for a total time complexity of O(m*log(m)), where 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.sort will likely run faster than a custom integer 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 contains operation 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)).
The following is untested. Implementation of isInt left as an exercise.
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.
这篇关于检查，如果在一个阵列的每个元素是在第二阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
