我有两个数组,我想检查是否每个元素arr2都在中arr1。如果元素的值在中重复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
一种选择是对两个数组进行排序,然后遍历两个数组,然后比较元素。如果在超级袋中未找到子袋候选中的元素,则前者不是子袋。排序通常为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; }
如果实际代码中的元素是整数,则可以使用特殊的整数排序算法(例如radixsort)来解决总体O(max(s,t))时间复杂度,尽管如果包很小,则构建-in的Array.sort运行速度可能会比自定义整数排序快。
Array.sort
一种可能具有较小的时间复杂性的解决方案是创建一个袋类型。整数袋特别容易。翻转袋子的现有数组:创建一个对象或一个以整数为键并重复计数值的数组。因此不会浪费空间。您可以将行李操作用于子行李或超级行李检查。例如,从次要候选者中减去上级,然后测试结果是否为空。或者,contains操作应为O(1)(或可能为O(log(n))),因此循环遍历子袋候选物并测试超级袋容纳量是否超过每个子袋元素的子袋容纳量应该是O(n)或O(n* log(n))。
contains
以下未经测试。执行isInt左为练习。
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); })); };