JavaScript配列の重い6つの方法
方法1
考えなくても、O(n^2)複雑度の解法が得られます。変数配列resの保存結果を定義します。巡回は、resの中に既に存在している場合、重複した要素であることを示します。ない場合は、resに入れます。
法1は、元の配列の要素と結果配列の要素を一つずつ比較し、考えを変えて、元の配列の重複要素の最後の要素を結果配列に入れることができます。
方法三(sort)
筆記試験の面接で上記のようなO(n^2)の案しか答えられなかったら、まだ面接官を満足させることができないかもしれません。
配列をsortで並べ替えると、理論的に同じ元素が隣の位置に置かれます。前後の位置の元素を比較すればいいです。
方法四(object)
JavaScriptのObjectオブジェクトを使ってハッシュ表として使用します。これも数年前の筆記試験時の解法です。sortと同じように、完全にNumberの基本タイプからなる配列を重くすることができます。
方法5(ES 6)
ES 6はSetとAray.fromの方法を展開しています。強すぎます。ブラウザがサポートすれば、このようにすることができます。
最後にアンダースコアのこれに対する実現方式を見にきて、アンダースコアはこれを_にカプセル化しました。uniqueメソッドでは、呼び出し方式は_.unique(array,[isSorted],[iteratee])。最初のパラメータは必要であり、重い配列が必要であり、第二のパラメータはオプションであり、配列が規則化されていれば、ブール値trueに入ることができ、第三のパラメータは任意であり、配列の反復の結果を再入力する必要があれば、反復関数に入ることができる。配列要素のデキストは==演算子に基づいています。
実はとても簡単で、アンダースコアの中の実現方式は上の方法と同じです。
コアコードを見に来ました。
以上が本文の全部です。本文の内容は皆さんの学習や仕事に一定の助けをもたらしてくれると同時に、私達を応援してください。
考えなくても、O(n^2)複雑度の解法が得られます。変数配列resの保存結果を定義します。巡回は、resの中に既に存在している場合、重複した要素であることを示します。ない場合は、resに入れます。
function unique(a) {
var res = [];
for (var i = 0, len = a.length; i < len; i++) {
var item = a[i];
for (var j = 0, jLen = res.length; j < jLen; j++) {
if (res[j] === item)
break;
}
if (j === jLen)
res.push(item);
}
return res;
}
var a = [1, 1, '1', '2', 1];
var ans = unique(a);
console.log(ans); // => [1, "1", "2"]
コードはとても簡単です。もっと簡潔にしてもらえますか?ブラウザ互換性を考慮しないなら、ES 5が提供するAray.prototype.indexOf法でコードを簡略化できます。
function unique(a) {
var res = [];
for (var i = 0, len = a.length; i < len; i++) {
var item = a[i];
(res.indexOf(item) === -1) && res.push(item);
}
return res;
}
var a = [1, 1, '1', '2', 1];
var ans = unique(a);
console.log(ans); // => [1, "1", "2"]
indexOfを使った以上、filterを追加してもいいです。
function unique(a) {
var res = a.filter(function(item, index, array) {
return array.indexOf(item) === index;
});
return res;
}
var a = [1, 1, '1', '2', 1];
var ans = unique(a);
console.log(ans); // => [1, "1", "2"]
方法2法1は、元の配列の要素と結果配列の要素を一つずつ比較し、考えを変えて、元の配列の重複要素の最後の要素を結果配列に入れることができます。
function unique(a) {
var res = a.filter(function(item, index, array) {
return array.indexOf(item) === index;
});
return res;
}
var a = [1, 1, '1', '2', 1];
var ans = unique(a);
console.log(ans); // => [1, "1", "2"]
複雑さはまだO(n^2)ですが、1は配列の一番後ろに現れています。結果配列は元素の最後の出現の位置を取っています。方法三(sort)
筆記試験の面接で上記のようなO(n^2)の案しか答えられなかったら、まだ面接官を満足させることができないかもしれません。
配列をsortで並べ替えると、理論的に同じ元素が隣の位置に置かれます。前後の位置の元素を比較すればいいです。
function unique(a) {
return a.concat().sort().filter(function(item, pos, ary) {
return !pos || item != ary[pos - 1];
});
}
var a = [1, 1, 3, 2, 1, 2, 4];
var ans = unique(a);
console.log(ans); // => [1, 2, 3, 4]
しかし、問題はまた来ました。1と1は並べられます。Objectは同じ結果になります。
function unique(a) {
return a.concat().sort().filter(function(item, pos, ary) {
return !pos || item != ary[pos - 1];
});
}
var a = [1, 1, 3, 2, 1, 2, 4, '1'];
var ans = unique(a);
console.log(ans); // => [1, 2, 3, 4]
もちろん、この比較関数は、行列に現れる可能性のある異なるタイプに対して完全に記述できます。でも、これはちょっと面倒くさいようです。方法四(object)
JavaScriptのObjectオブジェクトを使ってハッシュ表として使用します。これも数年前の筆記試験時の解法です。sortと同じように、完全にNumberの基本タイプからなる配列を重くすることができます。
function unique(a) {
var seen = {};
return a.filter(function(item) {
return seen.hasOwnProperty(item) ? false : (seen[item] = true);
});
}
var a = [1, 1, 3, 2, 1, 2, 4];
var ans = unique(a);
console.log(ans); // => [1, 3, 2, 4]
やはり方法三と同じ問題です。Objectのkey値は全部Stringタイプですから、1と「1」の区別ができません。少し改善して、タイプもkeyに入れます。
function unique(a) {
var ret = [];
var hash = {};
for (var i = 0, len = a.length; i < len; i++) {
var item = a[i];
var key = typeof(item) + item;
if (hash[key] !== 1) {
ret.push(item);
hash[key] = 1;
}
}
return ret;
}
var a = [1, 1, 3, 2, '4', 1, 2, 4, '1'];
var ans = unique(a);
console.log(ans); // => [1, 3, 2, "4", 4, "1"]
嫌な1と1の問題を解決しましたが、他の問題があります。
function unique(a) {
var ret = [];
var hash = {};
for (var i = 0, len = a.length; i < len; i++) {
var item = a[i];
var key = typeof(item) + item;
if (hash[key] !== 1) {
ret.push(item);
hash[key] = 1;
}
}
return ret;
}
var a = [{name: "hanzichi"}, {age: 30}, new String(1), new Number(1)];
var ans = unique(a);
console.log(ans); // => [Object, String]
しかし、配列要素が全部基礎タイプのNumberの値なら、キーの対法は一番効率的であるべきです。方法5(ES 6)
ES 6はSetとAray.fromの方法を展開しています。強すぎます。ブラウザがサポートすれば、このようにすることができます。
function unique(a) {
return Array.from(new Set(a));
}
var a = [{name: "hanzichi"}, {age: 30}, new String(1), new Number(1)];
var ans = unique(a);
console.log(ans); // => [Object, Object, String, Number]
_.unique最後にアンダースコアのこれに対する実現方式を見にきて、アンダースコアはこれを_にカプセル化しました。uniqueメソッドでは、呼び出し方式は_.unique(array,[isSorted],[iteratee])。最初のパラメータは必要であり、重い配列が必要であり、第二のパラメータはオプションであり、配列が規則化されていれば、ブール値trueに入ることができ、第三のパラメータは任意であり、配列の反復の結果を再入力する必要があれば、反復関数に入ることができる。配列要素のデキストは==演算子に基づいています。
実はとても簡単で、アンダースコアの中の実現方式は上の方法と同じです。
コアコードを見に来ました。
for (var i = 0, length = getLength(array); i < length; i++) {
var value = array[i],
//
//
computed = iteratee ? iteratee(value, i, array) : value;
// ,
// seen
if (isSorted) {
// i === 0, push
//
if (!i || seen !== computed) result.push(value);
// seen ,
seen = computed;
} else if (iteratee) {
// seen[] computed
if (!_.contains(seen, computed)) {
seen.push(computed);
result.push(value);
}
} else if (!_.contains(result, value)) {
// , seen[]
result.push(value);
}
}
外部の循環は配列要素を遍歴し、各要素に対して、配列が整然としていれば、前の要素と比較し、同じであれば、すでに現れています。結果配列には加入していません。そうでなければ、加入します。反復関数がある場合は、着信反復関数の値を計算し、値を逆にして呼び出します。contains方法の核心は呼び出しです。indexOf方法は、上記の方法と同じです。以上が本文の全部です。本文の内容は皆さんの学習や仕事に一定の助けをもたらしてくれると同時に、私達を応援してください。