JavaScriptでサブ配列をマージする方法｜共通メールアドレスによるアカウント統合

JavaScriptでは、複数のサブ配列に分かれたデータを特定の条件をもとにひとつにまとめたい場面があります。本記事では、『同じメールアドレスを含むサブ配列同士をマージする』という定番問題を題材に、Map・Set・再帰処理（DFS）を使った実装方法をわかりやすく解説します。

問題設定

まず、何人かの「名前とメールアドレス」の情報を格納した、配列の中に配列が入ったデータ構造を用意します。

const arr = [
    ['John', 'johnsmith@mail.com', 'john00@mail.com'],
    ['John', 'johnnybravo@mail.com'],
    ['John', 'johnsmith@mail.com', 'john_newyork@mail.com'],
    ['Mary', 'mary@mail.com']
];

各要素は文字列のサブ配列になっており、先頭の要素が名前、2番目以降の要素がその名前に紐づくメールアドレスを表しています。

マージのルール

• 共通するメールアドレスが1つでもあれば、そのサブ配列同士は同一人物のものとしてマージできる。
• 名前が同じでも別人の可能性がある。同姓同名の人は現実に存在するため、名前だけでは判断できません。
• 1人が持つアカウントの数は任意だが、すべてのアカウントで名前は必ず同じである。

期待される出力形式

マージ後の各サブ配列は、先頭に名前、続けてソート済みのメールアドレスを並べます。サブ配列自体の順序は任意です。上記の入力に対する出力は次のようになります。

const output = [
    ['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],
    ['John', 'johnnybravo@mail.com'],
    ['Mary', 'mary@mail.com']
];

1つ目と3つ目のサブ配列は 'johnsmith@mail.com' を共有しているため、Johnのメールアドレスが1つの配列に統合されている点に注目してください。一方、同じ「John」という名前でも 'johnnybravo@mail.com' だけを持つアカウントは共通のメールがないため、独立したサブ配列のままになっています。

実装のアプローチ

この問題は、グラフの連結成分を求める要領で解くことができます。全体の手順は以下のとおりです。

1. 各メールアドレスをキー、そのメールアドレスが登場するサブ配列のインデックスの一覧を値とするMapを作成する。
2. まだ処理していないサブ配列から深さ優先探索（DFS）で関係するメールアドレスをすべて収集する。共通のメールアドレスを介して間接的につながっているアカウントも、ここで漏れなくたどることができます。
3. 収集したメールアドレスをソートし、先頭に名前を付け加えて結果に追加する。

すでに処理済みのメールアドレスの管理にはSetを使うことで、同じメールの二重処理や重複登録を防げます。

コード例

const arr = [
    ['John', 'johnsmith@mail.com', 'john00@mail.com'],
    ['John', 'johnnybravo@mail.com'],
    ['John', 'johnsmith@mail.com', 'john_newyork@mail.com'],
    ['Mary', 'mary@mail.com']
];

// 共通のメールアドレスを頼りに、関連するメールを再帰的に収集する関数
const collectEmails = (visited, i, emailMap, arr, bucket) => {
    for (let j = 1; j < arr[i].length; j += 1) {
        const currentEmail = arr[i][j];
        if (visited.has(currentEmail)) continue;
        bucket.push(currentEmail);
        visited.add(currentEmail);

        // このメールを共有している他のアカウントも再帰的にたどる
        const relatedIndexes = emailMap.get(currentEmail);
        for (const otherIndex of relatedIndexes) {
            if (otherIndex !== i) {
                collectEmails(visited, otherIndex, emailMap, arr, bucket);
            }
        }
    }
};

const merge = (arr) => {
    // メールアドレス -> アカウントのインデックス一覧 の対応表を作成
    const emailMap = new Map();
    arr.forEach((account, i) => {
        for (let j = 1; j < account.length; j += 1) {
            const email = account[j];
            if (!emailMap.has(email)) emailMap.set(email, []);
            emailMap.get(email).push(i);
        }
    });

    const visited = new Set();
    const result = [];

    arr.forEach((account, i) => {
        const emails = [];
        collectEmails(visited, i, emailMap, arr, emails);
        // すべてのメールが既に処理済みの場合は空になるので、
        // 空でないときだけ結果に追加する
        if (emails.length) {
            emails.sort();
            emails.unshift(account[0]);
            result.push(emails);
        }
    });

    return result;
};

console.log(merge(arr));

実行結果

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

[
    [
        'John',
        'john00@mail.com',
        'john_newyork@mail.com',
        'johnsmith@mail.com'
    ],
    [ 'John', 'johnnybravo@mail.com' ],
    [ 'Mary', 'mary@mail.com' ]
]

ポイントのまとめ

• Mapで「メールアドレス → アカウント一覧」の対応を持たせることで、同じメールを共有するアカウントを即座に見つけられます。
• Setで訪問済みのメールを管理し、無駄な再帰や重複登録を防ぎます。
• すべてのメールがすでに処理済みのアカウントでは収集結果が空になるため、空でない場合だけ結果へ追加すれば十分です。
• 計算量は、メールアドレスの総数をEとすると、ソートのコストが支配的となりおおむねO(E log E)です。Mapの構築とDFSはそれぞれO(E)で完了します。