JavaScriptで2つの配列間の欠落した数値を見つける方法

問題の概要

2つの配列 arr1 と arr2 を引数として受け取るJavaScript関数を作成します。

arr2 は arr1 の要素をシャッフルした複製ですが、たった1つの要素だけが欠落しています。

この関数の目的は、その欠落している1つの要素を見つけ出して返すことです。

アプローチのポイント

最もシンプルかつ効率的なのは、ハッシュマップ（オブジェクト）を使って各数値の出現回数を記録する方法です。計算量は O(n) に抑えられ、配列内に重複した値が含まれていても正しく動作します。

コード例

以下が実際のコードです。

const arr1 = [6, 1, 3, 6, 8, 2];
const arr2 = [3, 6, 6, 1, 2];
const findMissing = (arr1 = [], arr2 = []) => {
   const obj = {};
   for (let i = 0; i < arr1.length; i++) {
      if (obj[arr1[i]] === undefined) {
         obj[arr1[i]] = 1;
      } else {
         obj[arr1[i]]++;
      };
   }
   for (let i = 0; i < arr2.length; i++) {
      if (obj[arr2[i]] === undefined || obj[arr2[i]]-- === 0) {
         return arr2[i];
      }
   }
   for (key in obj) {
      if (obj[key] > 0) {
         return Number(key);
      }
   }
   return -1;
};
console.log(findMissing(arr1, arr2));

出力結果

コンソールには次のように出力されます。

8

コードの解説

このコードの処理の流れは以下のとおりです。

1. 最初のループで、arr1 の各要素の出現回数をオブジェクト obj に記録します。
2. 次のループでは、arr2 側に余分な要素（arr1 に存在しない、または個数が超過している要素）がないかをチェックします。
3. 最後のループで、obj の中にカウントが 0 より大きいまま残っているキー、すなわち「arr1 には存在するが arr2 には存在しない要素」を探して返します。

今回の例では、8 が arr1 に含まれている一方で arr2 には存在しないため、8 が答えとして出力されます。該当する要素が見つからなかった場合の保険として、関数は最後に -1 を返すようになっています。

補足：別の解き方

重複した値が含まれないことが保証されている場合は、両配列の合計値の差分を取る方法や、XOR（排他的論理和）を利用する方法でも欠落した数値を求めることができます。ただし、本記事のように重複を許容するケースでは、出現回数をカウントするハッシュマップ方式が最も確実なアプローチといえます。