JavaScript 学習メモ: 配列重複排除_JavaScript スキル

推奨読書: JavaScript 学習ノート: 配列の追加、削除、変更、チェック

JavaScript 学習メモ Array Sum メソッド

JavaScript 学習ノート配列のランダムな並べ替え

面接では、面接官が JavaScript での配列の重複排除の実装についてよく質問します。最近、たまたま JavaScript の配列について学習していたので、この機会に JavaScript で配列の重複排除を行う方法をいくつか整理してみました。

以下の配列の重複排除方法は、私が独自に収集・整理したものです。間違いがあれば、本文中の間違いをご指摘ください。

ダブルループ重複排除

このメソッドは、走査に 2 つの for ループを使用します。全体的なアイデアは次のとおりです:

重複排除された配列を保存する空の配列を構築します

外側の for ループは元の配列を走査し、毎回配列から要素を取り出し、結果の配列と比較します
元の配列から取り出した要素が結果配列の要素と同じである場合はループを抜け、それ以外の場合は結果配列

に格納します。

コードは次のとおりです:

Array.prototype.unique1 = function () {
// 构建一个新数组，存放结果
var newArray = [this[0]];
// for循环，每次从原数组中取出一个元素
// 用取出的元素循环与结果数组对比
for (var i = 1; i < this.length; i++) {
var repeat = false;
for (var j=0; j < newArray.length; j++) {
// 原数组取出的元素与结果数组元素相同
if(this[i] == newArray[j]) {
repeat = true;
break;
}
}
if(!repeat) {
// 如果结果数组中没有该元素，则存放到结果数组中
newArray.push(this[i]);
}
}
return newArray;
}

次のような配列があるとします。

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1',`2`];
arr.unique1(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5]

この方法は時間がかかり、パフォーマンスが高いと言われています。簡単なテストを実行してください (テストメソッドの書き方が不十分です):

function test () {
var arr = [];
for (var i = 0; i < 1000000; i++) {
arr.push(Math.round(Math.random(i) * 10000));
}
doTest(arr, 1);
}
function doTest(arr, n) {
var tStart = (new Date()).getTime();
var re = arr.unique1();
var tEnd = (new Date()).getTime();
console.log('双重循环去重方法使用时间是:' + (tEnd - tStart) + 'ms');
return re;
}
test();

Chrome コントローラーで上記のコードを実行し、二重ループの重複排除にかかる時間をテストします: 11031 ミリ秒。

上記のメソッドは、forEach() メソッドとindexOf() メソッドを使用してシミュレートできます。

function unique1() {
var newArray = [];
this.forEach(function (index) {
if (newArray.indexOf(index) == -1) {
newArray.push(index);
}
});
return newArray;
}

unique1.apply(arr) または unique1.call(arr) 経由で呼び出します。ただし、この方法の方がはるかに効率的です。上記の同じテスト コードでは 5423 ミリ秒かかります。これはほぼ半分の速度です。

重複を削除するための走査の並べ替え

まず、sort() メソッドを使用して元の配列を並べ替えます。並べ替えた後、配列を走査し、配列の i 番目の要素が結果の配列の最後の要素と同じかどうかを確認します。異なる場合、要素は結果の配列に配置されます。

Array.prototype.unique2 = function () {
// 原数组先排序
this.sort();
// 构建一个新数组存放结果
var newArray = [];
for (var i = 1; i < this.length; i++) {
// 检查原数中的第i个元素与结果中的最后一个元素是否相同
// 因为排序了，所以重复元素会在相邻位置
if(this[i] !== newArray[newArray.length - 1]) {
// 如果不同，将元素放到结果数组中
newArray.push(this[i]);
}
}
return newArray;
}

例:

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique2(); // ["1", 1, 2, "2", 3, 32, 34, 4, 5, 56, "a", "b", "c"]

このメソッドには 2 つの特徴があります:

主に元の数値が重複排除前にソートされているため、重複排除後の配列はソートされます

重複排除後の配列では、「1」と1など、数字と同じ数字は区別できません

同じ方法を使用した場合のテスト時間は 1232ms です。

オブジェクトのキーと値のペアのメソッド

この重複排除方法の実装アイデアは次のとおりです:

JavaScript オブジェクトと新しい配列を作成します

for ループを使用して元の配列を走査し、毎回 1 つの要素を取り出して JavaScript オブジェクトのキーと比較します

含まれていない場合は、オブジェクトに格納されている要素の値を結果配列にプッシュし、オブジェクト object に格納されている属性名の値を 1 に設定します

コードは次のとおりです:

Array.prototype.unique3 = function () {
// 构建一个新数组存放结果
var newArray = [];
// 创建一个空对象
var object = {};
// for循环时，每次取出一个元素与对象进行对比
// 如果这个元素不重复，则将它存放到结果数中
// 同时把这个元素的内容作为对象的一个属性，并赋值为1,
// 存入到第2步建立的对象中
for (var i = 0; i < this.length; i++){
// 检测在object对象中是否包含遍历到的元素的值
if(!object[typeof(this[i]) + this[i]]) {
// 如果不包含，将存入对象的元素的值推入到结果数组中
newArray.push(this[i]);
// 如果不包含，存入object对象中该属性名的值设置为1
object[typeof(this[i]) + this[i]] = 1;
}
}
return newArray;
}

前の例を実行します:

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique3(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5, "1", "2"]

同様に、異なるキーが同じものと誤認される可能性があります。たとえば、 a[1]、a["1"] です。この方法でかかる時間: 621ms。 この方法では所要時間は最も短くなりますが、より多くのメモリを消費します。

上記の方法以外にも、次のような方法があります。

// 方法四
Array.prototype.unique4 = function () {
// 构建一个新数组存放结果
var newArray = [];
// 遍历整个数组
for (var i = 0; i < this.length; i++) {
// 遍历是否有重复的值
for (j = i + 1; j < this.length; j++) {
// 如果有相同元素，自增i变量，跳出i的循环
if(this[i] === this[j]) {
j = ++i;
}
}
// 如果没有相同元素，将元素推入到结果数组中
newArray.push(this[i]);
}
return newArray;
}

Chrome テスト結果

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique4(); // ["a", 1, 3, 4, 56, 32, 34, 2, "b", "c", 5, "1", "2"]

同様に、1 と '1' は区別できません。

// 方法五
Array.prototype.unique5 = function () {
// 构建一个新数组存放结果
var newArray = [];
// 遍历整个数组
for (var i = 0; i < this.length; i++) {
// 如果当前数组的第i值保存到临时数组，那么跳过
var index = this[i];
// 如果数组项不在结果数组中，将这个值推入结果数组中
if (newArray.indexOf(index) === -1) {
newArray.push(index);
}
}
return newArray;
}

Chrome テスト結果:

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique6(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5, "1", "2"]

同様に、1 と '1' は区別できません。費やした時間: 14361ms。

// 方法六
Array.prototype.unique6 = function () {
return this.reduce(function (newArray, index) {
if(newArray.indexOf(index) < 0) {
newArray.push(index);
}
return newArray;
},[]);
}

テスト結果は次のとおりです:

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique6(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5, "1", "2"]

所要時間: 16490ミリ秒。

// 方法七
Array.prototype.unique7 = function(){
var newArray;
newArray = this.filter(function (ele,i,arr) {
return arr.indexOf(ele) === i;
});
return newArray;
}

テスト結果:

var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2'];
arr.unique6(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5, "1", "2"]

所要時間: 13201ms。

多くの方法がありますが、比較すると、次の方法がより良い解決策です:

Array.prototype.unique3 = function () {
// 构建一个新数组存放结果
var newArray = [];
// 创建一个空对象
var object = {};
// for循环时，每次取出一个元素与对象进行对比
// 如果这个元素不重复，则将它存放到结果数中
// 同时把这个元素的内容作为对象的一个属性，并赋值为1,
// 存入到第2步建立的对象中
for (var i = 0; i < this.length; i++){
// 检测在object对象中是否包含遍历到的元素的值
if(!object[typeof(this[i]) + this[i]]) {
// 如果不包含，将存入对象的元素的值推入到结果数组中
newArray.push(this[i]);
// 如果不包含，存入object对象中该属性名的值设置为1
object[typeof(this[i]) + this[i]] = 1;
}
}
return newArray;
}

しかし、ES6 には次のような、よりシンプルでより最適化された重複排除ソリューションがあります。

// ES6
function unique (arr) {
const seen = new Map()
return arr.filter((a) => !seen.has(a) && seen.set(a, 1))
}
// or
function unique (arr) {
return Array.from(new Set(arr))
}

上記は、配列から重複を削除するためにエディターが紹介した JavaScript の学習メモです。