У меня есть два массива, и я хочу проверить, находится ли каждый элемент в 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;
}
Если элементы в реальном коде являются целыми числами, вы можете использовать специальный целочисленный алгоритм сортировки (такой как сортировка по основанию) для общей сложности времени O (max (s, t)), хотя, если мешки малы, встроенная -in Array.sort, вероятно, будет работать быстрее, чем пользовательская целочисленная сортировка.
Решение с потенциально меньшей временной сложностью заключается в создании типа сумки. Целочисленные сумки особенно просты. Переверните существующие массивы для сумок: создайте объект или массив с целыми числами в качестве ключей и счетчиком повторений для значений. Использование массива не приведет к потере пространства, так как массивы в Javascript редки. Вы можете использовать операции с сумками для проверки сумок или сумок. Например, вычтите супер из вспомогательного кандидата и проверьте, что результат не пустой. В качестве альтернативы, contains операции должно быть O (1) (или, возможно, O (журнал (п))), так что цикл над кандидата суб-мешок и тестирования, если супер-мешка защитной оболочки превышает суб-мешок сдерживания для каждого суб-мешок элемент должен быть 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 " для примера реализации набора объектов, если вы когда-нибудь захотите запретить повторение элементов.
Вам нужно поддерживать мучительные браузеры? Если нет, функция every должна сделать это легко.
Если arr1 является надмножеством arr2, то каждый член в arr2 должен присутствовать в arr1
var isSuperset = arr2.every(function(val) { return arr1.indexOf(val) >= 0; });
Здесь fiddle
ИЗМЕНИТЬ
Итак, вы определяете супермножество таким образом, что для каждого элемента в arr2 оно встречается в arr1 одинаковое количество раз? Я думаю, что filter поможет вам это сделать (возьмите прокладку из предыдущей ссылки 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;
});
END EDIT
Если вы хотите поддерживать более старые браузеры, ссылка 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 2), поэтому избегайте его запуска на больших массивах.
Никто еще не опубликовал рекурсивную функцию, и это всегда весело. Назовите его как 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 );
};
Использование объектов (чтение: хеш-таблицы) вместо сортировки должно уменьшить степень амортизации до 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.
Нашел это в библиотеке 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Если 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
Что касается другого подхода, вы можете сделать следующее:
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));Вот мое решение:
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
Быстрое решение здесь принимает два массива, если b длиннее, чем не может быть супер-set, поэтому возвращаем 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.
небольшая версия:
function checkSuperbag(arr1, arr2) {
return !!~arr2.join('').indexOf(arr1.join(''))
}