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

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

一种选择是对两个数组进行排序，然后遍历两个数组，然后比较元素。如果在超级袋中未找到子袋候选中的元素，则前者不是子袋。排序通常为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））时间复杂度，尽管如果bag很小，则构建-
in的

Array.sort

运行速度可能会比自定义整数排序快。

一种可能具有较小的时间复杂性的解决方案是创建一个袋类型。整数袋特别容易。翻转袋子的现有数组：创建一个对象或一个以整数为键并重复计数值的数组。使用数组不会因为Javascript中的数组稀疏而创建，因此不会浪费空间。您可以将行李 *** 作用于子行李或超级行李检查。例如，从次要候选者中减去上级，然后测试结果是否为空。或者，

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) {  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数组
”以获取一组对象的示例实现。