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

Harry
2011-12-25  
37564  
    
10  

我有两个数组，我想检查 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
javascript ,  arrays ,  node.js
stack overflow Check if every element in one array is in a second array
原文答案
author avatar
outis
2011-12-25
25
     原文

接受的答案

一种选择是对两个数组进行排序，然后遍历两者，比较元素。如果在超级包中没有找到子包候选中的元素，则前者不是子包。排序一般是 O(nlog(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)) 时间复杂度，但如果袋子很小，内置的 Array.sort 可能会比自定义整数排序运行得更快。

一种时间复杂度可能较低的解决方案是创建一个袋子类型。整数袋特别容易。翻转袋子的现有数组：创建一个对象或数组，其中整数作为键，重复计数作为值。通过创建为 arrays are sparse in Javascript 使用数组不会浪费空间。您可以将包操作用于子包或超级包检查。例如，从 sub 候选中减去 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 ”以获取一组对象的示例实现。


答案:

作者头像
Adam Rackis
2011-12-25    36      原文

你必须支持糟糕的浏览器吗？如果没有， every 函数应该让这变得简单。

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

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

这是一个 fiddle

编辑

因此，您正在定义超集，以便对于 arr2 中的每个元素，它在 arr1 中出现的次数相同？我认为 filter 将帮助您做到这一点（从前面的 MDN 链接中获取 shim 以支持旧浏览器）：

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

Updated Fiddle

结束编辑

如果您确实想支持较旧的浏览器，上面的 MDN 链接有一个您可以添加的 shim，为了您的方便，我在这里复制它：

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(N2) 算法，因此请避免在大型数组上运行它。

作者头像
ThinkingStiff
2011-12-26    6      原文

还没有人发布递归功能，这些功能总是很有趣。称其为 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 );

};
作者头像
Ashish Singh Rawat
2018-06-14    5      原文

在 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
作者头像
mzedeler
2013-03-21    4      原文

使用对象（阅读：哈希表）而不是排序应该将摊销复杂度降低到 O(m+n)：

function bagContains(arr1, arr2) {
    var o = {}
    var result = true;

    // Count all the objects in container
    for(var i=0; i < arr1.length; i++) {
        if(!o[arr1[i]]) {
            o[arr1[i]] = 0;
        }
        o[arr1[i]]++;
    }

    // Subtract all the objects in containee
    // And exit early if possible
    for(var i=0; i < arr2.length; i++) {
        if(!o[arr2[i]]) {
            o[arr2[i]] = 0;
        }
        if(--o[arr2[i]] < 0) {
            result = false;
            break;
        }
    }

    return result;
}

console.log(bagContains([1, 2, 3, 4], [1, 3]));
console.log(bagContains([1, 2, 3, 4], [1, 3, 3]));
console.log(bagContains([1, 2, 3, 4], [1, 3, 7]));

这会产生 true 、 false 、 false 。

作者头像
SuperNova
2017-12-12    2      原文

如果ARR2是ARR1的子集，则 Length of set(arr1 + arr2) == Length of set(arr1) 

var arr1 = [1, 'a', 2, 'b', 3];
var arr2 = [1, 2, 3];

Array.from(new Set(arr1)).length == Array.from(new Set(arr1.concat(arr2))).length
作者头像
Redu
2017-06-20    1      原文

至于另一种方法，您可以执行以下操作；

function checkIn(a,b){
  return b.every(function(e){
                   return e === this.splice(this.indexOf(e),1)[0];
                 }, a.slice()); // a.slice() is the "this" in the every method
}

var arr1  = [1, 2, 3, 4],
    arr2  = [1, 2],
    arr3  = [1,2,3,3];
console.log(checkIn(arr1,arr2));
console.log(checkIn(arr1,arr3));
作者头像
Cholakov
2018-01-24    1      原文

这是我的解决方案：

Array.prototype.containsIds = function (arr_ids) {
    var status = true;
    var current_arr = this;
    arr_ids.forEach(function(id) {
        if(!current_arr.includes(parseInt(id))){
            status = false;
            return false; // exit forEach
        }
    });
    return status;
};

// Examples
[1,2,3].containsIds([1]); // true
[1,2,3].containsIds([2,3]); // true
[1,2,3].containsIds([3,4]); // false
作者头像
qw3n
2011-12-25    0      原文

如果 b 长于它不能是超集，则此处的快速解决方案采用两个数组，因此返回 false。然后循环 b 以查看 a 是否包含该元素。如果是这样，将其从 a 中删除，如果不返回 false，则继续。更糟糕的情况是如果 b 是一个子集，那么时间将是 b.length 。

function isSuper(a,b){
  var l=b.length,i=0,c;
  if(l>a.length){return false}
  else{
    for(i;i<l;i++){
      c=a.indexOf(b[i]);
      if(c>-1){
        a.splice(c,1);
      }
      else{return false}
    }
    return true;
  }
}

这假设输入并不总是按顺序排列，如果 a 是 1,2,3 并且 b 是 3,2,1 它仍然会返回 true。

作者头像
Pontios
2020-12-07    0      原文

另一个简单的解决方案如下：

let a = [1,2,'a',3,'b',4,5]

let b = [1,2,4]

console.log(b.every((i) => a.includes(i)))

希望能帮助到你

相关问题

标签