JavaScriptで配列内の同じ値のペアを数える方法

本記事では、重複した値を含む可能性のある整数の配列を受け取り、その中から同じ値どうしのペアがいくつ作れるかを求めるJavaScript関数の実装方法を解説します。

問題の概要

たとえば、次のような入力配列が与えられたとします。

const arr = [1, 5, 2, 1, 6, 2, 2, 9];

この場合、期待される出力は次のとおりです。

const output = 2;

これは、配列内に「1と1」「2と2」というペアがそれぞれ1組ずつ存在するためです。なお、2は3つあるため1つは余りますが、ペアとしては1組とカウントされます。

アルゴリズムの考え方

この問題を解く最もシンプルなアプローチは、以下の手順に従うことです。

1. 元の配列を変更しないよう、slice()でシャローコピーを作成します。
2. コピーした配列を昇順にソートします。ソート後は同じ値が必ず隣り合って並びます。
3. 隣接する2つの要素を比較し、等しければペアとしてカウントし、インデックスを2つ進めます（すでに使った値を再度数えないため）。

この方法の計算量はソート処理が支配的となるため、O(n log n)となります。データ量がそこまで多くないケースでは十分に高速で、可読性も高い実装です。

コード例

実際のコードは次のとおりです。

const arr = [1, 5, 2, 1, 6, 2, 2, 9];

const countPairs = (arr = []) => {
    const { length } = arr;
    let count = 0;
    // シャローコピーを作成し、元の配列が変更されないようにする
    const copy = arr.slice();
    copy.sort((a, b) => a - b);
    for (let i = 0; i < length; i++) {
        if (copy[i] === copy[i + 1]) {
            i++;
            count++;
        }
    }
    return count;
};

console.log(countPairs(arr));

実行結果

上記のコードをコンソールで実行すると、次の出力が得られます。

2

配列 [1, 5, 2, 1, 6, 2, 2, 9] には同じ値のペアが2組（1のペアと2のペア）含まれているため、正しく 2 が出力されます。

まとめ

ソートして隣接要素を比較するだけのシンプルなアルゴリズムでも、配列内の同一値ペアを効率よく数えられます。元の配列を破壊しないようコピーを取る点と、ペア成立時にインデックスを2つ進める点が実装上のポイントです。より大規模なデータを扱う場合は、オブジェクトやMapを使って各値の出現回数を集計し、「回数 ÷ 2 の切り捨て」を合計する手法（計算量O(n)）も検討するとよいでしょう。