2つの配列があり、arr2のすべての要素がarr1にあるかどうかをチェックしたいと思います。要素の値がarr2で繰り返される場合は、同じ回数でarr1になる必要があります。これを行う最善の方法は何ですか？1つの配列のすべての要素が2番目の配列にあるかどうかを確認します
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
2つの配列をソートし、両方の要素を比較して比較します。サブバッグ候補の要素がスーパーバッグに見つからない場合、前者はサブバッグではない。一般的にO（n * log（n））のソートはO（max * log（n））であり、O（max * s）の合計時間計算量はsとtである。 （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））の時間複雑さのために（例えばradix sortなど）専用の整数ソートアルゴリズムを使用できるかどうかのバッグが小さい場合、組み込みのArray.sortはカスタム整数型ソートよりも高速に実行される可能性が高くなります。
潜在的に時間の複雑さが低い可能性のある解決策は、バッグタイプを作成することです。完全なバッグは特に簡単です。バッグの既存の配列を反転させます：整数またはキーを持つオブジェクトまたは配列を作成し、値の繰り返し回数を作成します。配列を使用すると、arrays are sparse in Javascriptという名前をつけることでスペースを無駄にすることはありません。サブバッグまたはスーパーバッグのチェックには、バッグ操作を使用できます。たとえば、サブ候補からスーパーを減算し、結果が空でないかどうかをテストします。あるいは、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」も参照してください、あなたは今までの要素の繰り返しを禁止したいはずです。
「の運動として残っている」=「私は気にすることはできません」:) – derekdreery
@derekdreery：私の誇りを攻撃すると、私が割り当てた宿題に答えが出るとは思わない。私はあなたのトリックに賢明です;） – outis
クラミーブラウザをサポートする必要がありますか？そうでなければ、every関数はこれを簡単にするはずです。
ARR1はARR2のスーパーセットである場合は、ARR2で各メンバーがARR1ここ
var isSuperset = arr2.every(function(val) { return arr1.indexOf(val) >= 0; });
内に存在しなければならないだからあなたは、このようなスーパーセットを定義しているfiddle
EDIT
ですarr2の各要素に対して、arr1に同じ回数が発生していますか？あなたが望むならば
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
：私はfilterはあなたが（古いブラウザをサポートするために、先行するMDNのリンクからシムをつかむ）ことを行うのに役立ちますだと思います古いブラウザをサポートするために、上のMDNリンクにあなたが追加できるシムがあります。私はあなたの便宜のためにここに再現しています：
これはO（N 2 ）アルゴリズムであるので、大きなアレイ上で実行する回避すること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;
};
}
EDIT
注意。
これは 'O（N * N *）' –
@parapurarajkumarです - はい、そうです。私は大きい入力でこれを使用することについて私の答え警告OPに編集を追加します –
ありがとうアダム私は私の質問を少し編集しました、私は同じメンバーの倍数を同様にチェックする必要があります。最後の例を再。ありがとう – Harry
ここでは、bがスーパーセットではない場合は2つの配列を取るので、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が、それはまだtrueを返します3,2,1です。
誰もまだ再帰関数を投稿していません。それらは、常に楽しいものです。それを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。
別の方法として、次のようにすることができます。
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));小さなバージョン：
function checkSuperbag(arr1, arr2) {
return !!~arr2.join('').indexOf(arr1.join(''))
}
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
は私のソリューションです：
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
最後の例はfalseを返す必要があります。 2つの配列の長さが同じ場合、スーパー/サブセットはありません。 http://mathworld.wolfram.com/Superset.html – Bakudan
セットには重複要素を含めることはできません。そのため、これらの条件でスーパーセットであることを判断するという概念はあまり意味がありません。 –
最後の例は、2つの理由から、 'true'でなければなりません：（1）繰り返しは' {1,1} = {1} 'のセットでは関係ありません。 （2）集合はそれ自身の部分集合とスーパー集合である。 2つが等しくないと思われる場合は、「適切なサブセット」および「適切なスーパーセット」と呼ばれます。 – outis