【プログラミングクイズ】配列に登場する過半数を占める数字の出力(多数決アルゴリズム)

問題

あなたには配列が渡されます。その配列には必ず過半数（つまり、配列の長さの半分を超える）を占める数字が1つだけ存在します。配列に登場するこの過占数の数字を出力する関数を作成してください。

例えば、以下の配列が渡されるとします

const nums = [2, 1, 1, 2, 3, 2, 2];

この場合、2を出力してください。

ルール

配列の要素は正の整数です。
配列の長さは1以上で、必ず過半数を占める数字が1つ存在します。

回答例

過半数を超える数字を出力する方法

数字の登場回数をオブジェクトに記録して、過半数を占める数字を出力する方法です。

const nums = [2, 1, 1, 2, 3, 2, 2];

function findMajority(nums) {
    const counts = {};
    const halfLength = nums.length / 2;

    for (let num of nums) {
        if (counts[num]) {
            counts[num]++;
        } else {
            counts[num] = 1;
        }
    }

    for (let num in counts) {
        if (counts[num] > halfLength) {
            return Number(num);
        }
    }
    
    return -1;
}

console.log(findMajority(nums));  // 2

最も出現回数の多い数字を返す方法

過半数を占めると言うことは、もっとも出現回数が多いと言うことです。なので登場した数字でもっとも出現回数の多い数字を出力する方法です。

const nums = [2, 1, 1, 2, 3, 2, 2];

function findMajority(nums) {
    const counts = {};

    for (let num of nums) {
        if (counts[num]) {
            counts[num]++;
        } else {
            counts[num] = 1;
        }
    }

    let majority = null;
    let maxCount = 0;
    for (let num in counts) {
        if (counts[num] > maxCount) {
            maxCount = counts[num];
            majority = Number(num);
        }
    }

    return majority;
}

console.log(findMajority(nums));  // 2

多数決アルゴリズムを使用する方法

最後に多数決アルゴリズムを利用する方法を紹介します。
多数決アルゴリズムはBoyer-Moore投票アルゴリズムとも言われます。配列の中で過半数を占める要素を見つけ出す、まさに今回の問題にドンピシャで使えるアルゴリズムになります。

多数決アルゴリズムの詳細

これを知識として身につけておけば、配列の中で過半数を超える要素を出力するのに最も効率的な方法を取ることが出来ます。

const nums = [2, 1, 1, 2, 3, 2, 2];

function findMajority(nums) {
    let count = 0;
    let candidate = 0;

    for (let num of nums) {
        if (count == 0) {
            candidate = num;
        }
        if (num == candidate) {
            count += 1;
        } else {
            count -= 1;
        }
    }

    return candidate;
}

console.log(findMajority(nums));  // 2

こちらのアルゴリズムは以下のように作用します。
アルゴリズムは以下のように動作します：

1. 最初に、配列の最初の要素を「候補」（candidate）として選択し、その出現回数（count）を1とする。
2. 次に、配列の次の要素を確認する。その要素が現在の候補と同じ場合、出現回数を1増やす。それが現在の候補と異なる場合、出現回数を1減らす。
3. 出現回数が0になった場合、次の要素を新たな候補とする。
4. これを配列の終わりまで繰り返す。
5. 配列をすべて見終わった時点での候補が、過半数を占める要素である。

---

以上が回答例になります。他にも効率の良い回答例があればコメントお待ちしております。