检查一个数组中的每个元素是否都在第二个数组中 [英] Check if every element in one array is in a second array

问题描述

我有两个数组，我想检查 arr2 中的每个元素是否都在 arr1 中.如果元素的值在 arr2 中重复，则它需要在 arr1 中重复相同的次数.这样做的最佳方法是什么?

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

推荐答案

一种选择是对两个数组进行排序，然后遍历两者，比较元素.如果在超级包中没有找到子包候选中的元素，则前者不是子包.排序一般是O(n*log(n))，比较是O(max(s,t))，其中s和t是数组大小，对于总时间复杂度为 O(m*log(m))，其中 m=max(s,t).

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;
}

如果实际代码中的元素是整数，可以使用特殊用途的整数排序算法(如radix sort) 的整体时间复杂度为 O(max(s,t))，但如果包很小，内置的 Array.sort 可能会比 a自定义整数排序.

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.

时间复杂度可能较低的解决方案是创建包类型.整数袋特别容易.翻转包的现有数组:创建一个对象或数组，以整数为键，重复计数值.使用数组不会浪费空间，因为 Javascript 中的数组是稀疏的.您可以使用包操作进行子包或超级包检查.例如，从子候选中减去 super 并测试结果是否为非空.或者，contains 操作应该是 O(1)(或可能是 O(log(n)))，因此循环遍历子包候选并测试超级包包含是否超过子包bag 对每个子包元素的包含应该是 O(n) 或 O(n*log(n)).

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)).

以下内容未经测试.isInt 的实现留作练习.

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);
           }));
};

另请参阅比较 javascript 数组"以获取一组对象的示例实现，如果您希望禁止元素的重复.

See also "comparing javascript arrays" for an example implementation of a set of objects, should you ever wish to disallow repetition of elements.

这篇关于检查一个数组中的每个元素是否都在第二个数组中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！