JavaScriptの「特別な配列」とは？判定アルゴリズムを実装して解説

プログラミングにおいて「特別な配列（Special Array）」と呼ばれる概念があります。本記事では、その定義と、JavaScriptで特別な配列を判定する関数の実装方法をわかりやすく解説します。

特別な配列の定義

ある配列が「特別な配列」であるとは、次の条件を満たす正の整数 num が存在する場合を指します。

配列内に、num より大きい要素がちょうど num 個存在すること。

ここで重要なポイントは、num 自体が必ずしも配列の要素である必要はないという点です。あくまで、そのような整数が存在すればよいのです。

具体例

例えば、次の入力配列を考えてみましょう。

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

この配列を注意深く観察すると、num = 3 のとき、3 より大きい要素は 5、7、9 のちょうど 3 個存在します。

つまり、「3 より大きい要素が 3 個ある」という条件が成立しており、この配列は特別な配列です。3 は配列の要素ではありませんが、定義上は問題ありません。

求められる処理の内容

今回実装するのは、数値の配列を受け取る JavaScript 関数です。関数の仕様は以下のとおりです。

• 配列が特別な配列であれば、その基準となる数値を返す
• 特別な配列でなければ、-1 を返す

実装コード

それでは、実際のコードを見てみましょう。

const arr = [2, 1, 5, 2, 7, 9];
const findSpecialArray = (array = []) => {
    const arr = array.slice().sort((a, b) => a - b);
    let index = 1;
    const { length } = arr;
    while(index <= arr[length-1]){
        let num = 0;
        for(let i=0; i<length; i++){
            if(arr[i] >= index){
                num++;
            }
        };
        if(num === index){ return index; };
        index++;
    };
    return -1;
};
console.log(findSpecialArray(arr));

出力結果

このコードを実行すると、次の出力が得られます。

3

アルゴリズムの流れを解説

コードの動作を順を追って整理してみましょう。

1. 配列のコピーとソート： 元の配列を変更しないよう slice() でコピーし、昇順にソートします。
2. 候補の探索： 候補となる数値 index を 1 から順に増やしながら調べます。探索範囲は最大要素までです。
3. 要素数のカウント： 各 index について、配列内の index 以上の要素数をカウントします。
4. 条件の判定： カウントした数と index が一致した時点で、その値を返します。
5. 該当なしの場合： すべての候補を調べても一致するものがなければ、-1 を返します。

この例の場合、index = 3 のときに 3 以上の要素（5、7、9）がちょうど 3 個見つかるため、戻り値は 3 となります。

まとめ

特別な配列の判定は、「ある数値以上の要素数」と「その数値自体」が一致する点を見つける問題です。シンプルな線形探索で実装できますが、ソート済み配列に対しては二分探索などを組み合わせることで、より効率的な実装も可能です。ぜひ自分のコードにも応用してみてください。