何回かに分けて、アルゴリズムの効率的な解法パターンをupしていこうと思います。

アルゴリズムは、力技でも解けるのですが、データ量が増えた時に、使い物にならなかったら悲しいですよね。

１回目は、最頻度カウンターパターン（勝手に命名）です。本noteでも何回か登場しています。

このパターンの目的は、２重ループ O(n^2)をなくすことです。

例えば、次の問題があったとします。

実行結果を見てみましょう。１つ目の引数を配列A、２つ目の引数を配列Bとします。

same([1,2,3],[4,1,9])  //true　配列Bには1*1 2*2 3*3 の結果が全て含まれいるのでtrueです。
same([1,2,3],[1,9])  //false　2*2=4が配列Bにないのでfalse
same([1,2,1],[4,4,1])  //false  配列Bの4になる2が配列Aにないのでfalse

二重ループ版 O(n^2)

function same(arr1, arr2) {
 if (arr1.length !== arr2.length) {
   return false;
 }

 for (let i = 0; i < arr1.length; i++) {
   let correctIndex = arr2.indexOf(arr1[i] ** 2);
   if (correctIndex === -1) {
     return false;
   }
   //console.log(arr2);
   arr2.splice(correctIndex, 1);
 }

 return true;
}

//console.log(same([1, 2, 3, 2], [9, 1, 4, 4]));

※forの内側にあるarr2.indexOf(arr1[i] ** 2);が２つ目のループです。

最初のforループで、配列Aを回していきます。ポイントは、arr2.indexOf(arr1[i] ** 2);で配列Bの中に、２乗した要素があるか評価しています。存在しない場合、indexOfは -1を返しますので、そこでfalseをreturn。

arr2.splice(correctIndex, 1);で該当する要素があった場合、チェックする配列Bの要素を減らしています。↓こんな感じですね。

[ 9, 1, 4, 4 ]
[ 9, 4, 4 ]
[ 9, 4 ]
[ 4 ]

結果、計算時間はO(n^2)なのであまりよろしくないです。配列A,B共に、データ量が10000になったらどうでしょうか？計算量は10000*10000になってしまいます。

さて、どうやったら二重ループをなくせるでしょうか？

最頻度カウンター適用版　O(n)

function same(arr1, arr2) {
 if (arr1.length !== arr2.length) {
   return false;
 }

 let frequencyCounter1 = {};
 let frequencyCounter2 = {};

　//カウンター生成
 for (let val of arr1) {
   frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
 }

 for (let val of arr2) {
   frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1;
 }

 //オブジェクト同士を評価
 for (let key in frequencyCounter1) {
   if (!(key ** 2 in frequencyCounter2)) {
     return false;
   }
   if (frequencyCounter2[key ** 2] !== frequencyCounter1[key]) {
     return false;
   }
 }

//console.log(frequencyCounter1);
//console.log(frequencyCounter2);
 return true;
}

//console.log(same2([1, 2, 3, 2], [9, 1, 4, 4]));

上のサンプルは、同じ問題を単一のループで解いた場合です。ポイントはkey・valueペアのオブジェクトを、あらかじめ用意することです。

配列A,BそれぞれにfrequencyCounter1、frequencyCounter2を用意していることに注目してください。

{ '1': 1, '2': 2, '3': 1 } //frequencyCounter1 元の配列[1, 2, 3, 2]
{ '1': 1, '4': 2, '9': 1 } //frequencyCounter2 元の配列[9, 1, 4, 4]

frequencyCounter1を見てみましょう。1は1回登場します。2は2回ですね。３も1回です。要素の登場数をデータとして準備しておきます。頻度のカウンターになってますよね。

あとはオブジェクト同士を比べていくだけです。keyが取れれば、単発のforループで評価できます。

・１つ目のif文でkey同士の評価（同じ要素か？）

・２つ目のif文で要素同士の評価（同じ頻度か？）

これで計算量が線形O(n)になりましたね。

なお、「ループが３つもあるじゃねえか？」と思うかもしれませんが、単一つ処理なので、はるかに高速です。それぞれデータ量が1000だとすると1000+1000+1000 = 3000回の処理になります。２重ループだったらどうでしょう？1000*1000で 1000000回の処理ですね。。。

どうでしたか？データ構造１つで、結果が劇的に変わるのを実感できたと思います。これがアルゴリズムのパワーです。

なぜGoogleやFacebookが面接で、アルゴリズムの問題を出すか理解できると思います。

扱うデータ量が圧倒的に大きいからです。

もう一問出しておくので、自力でチャレンジしてみよう。同じパターンで解けるはずです。

//出力結果
validAnagram('aaz','zza') //false
validAnagram('qwerty','qeywrt') //true

解答例：最頻度カウンター適用版　O(n)

function validAnagram(first, second) {
 if (first.length !== second.length) {
   return false;
 }

 const lookup = {};
 for (let i = 0; i < first.length; i++) {
   let letter = first[i];
   lookup[letter] ? (lookup[letter] += 1) : (lookup[letter] = 1);
 }

 for (let i = 0; i < second.length; i++) {
   let letter = second[i];
   if (!lookup[letter]) {
     return false;
   } else {
     lookup[letter] -= 1;
   }
 }

 return true;
}

//console.log(validAnagram("anagram", "nagaram"));

読み物としてハマります。一般化する思考が身につきます。

こちらも併せて読んでみてください！