Node.js 判断一个数组中的每个元素是否都在第二个数组中

一种 Select 是对两个数组进行排序，然后遍历这两个数组，比较元素.如果在超级包中找不到子包候选元素，则前者不是子包.排序通常为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(最大(s，t))时间复杂度，不过如果行李很小，内置Array.sort可能会比自定义整数排序运行得更快.

一个可能时间复杂度较低的解决方案是创建一个包类型.整型包特别容易.翻转行李的现有数组:创建一个对象或一个数组，将整数作为键，并对值进行重复计数.使用数组不会因为创建arrays are sparse in Javascript而浪费空间.您可以使用行李操作进行子行李或超级行李判断.例如，从子候选项中减go 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);
           }));
};

如果您希望禁止元素重复，请参见"comparing javascript arrays"以获取一组对象的示例实现.