检查一个数组中的每个元素是否都在第二个数组中

Question

我有两个数组,我想检查是否所有元素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

Answer 1

你必须支持糟糕的浏览器吗？如果没有,每个功能都应该让这一切变得简单.

如果arr1是arr2的超集,则arr2中的每个成员必须存在于arr1中

var isSuperset = arr2.every(function(val) { return arr1.indexOf(val) >= 0; });

这是一个小提琴

编辑

所以你要定义超集,这样对于arr2中的每个元素,它在arr1中出现的次数相同吗？我认为过滤器可以帮助你做到这一点(从前面的MDN链接获取垫片以支持旧浏览器):

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

更新小提琴

结束编辑

如果你想支持旧的浏览器,上面的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;  
  };  
}  

编辑

请注意,这将是一个O(N ²)算法,因此请避免在大型数组上运行它.

Answer 2

一种选择是对两个数组进行排序,然后遍历两个数组,比较元素.如果在超级包中没有找到子包候选中的元素,则前者不是子包.排序通常为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;
}

如果实际代码中的元素是整数,则可以使用特殊用途的整数排序算法(例如基数排序)来获得整体O(max(s,t))时间复杂度,但如果包很小,则构建-in Array.sort可能比自定义整数排序运行得更快.

具有可能较少时间复杂度的解决方案是创建袋类型.整数袋特别容易.翻转包的现有数组:创建一个对象或数组,其中整数为键,值为重复计数.使用数组不会因为Javascript中的数组稀疏而创建空间.您可以使用行李操作进行子行李或超级行李检查.例如,从子候选中减去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);
           }));
};

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

Answer 3

还没有人发布递归功能,这些功能总是很有趣.称之为arr1.containsArray( arr2 ).

演示: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 );

};

Answer 4

在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