【JavaScript】特殊文字の位置を固定したまま配列を反転するアルゴリズムの解法

問題の概要

今回は「配列を反転する関数を作成するが、配列内に含まれる特殊文字のインデックスは変更してはならない」という要件を持つアルゴリズム問題を取り上げます。

例として、特殊文字を「#」とすると、次の配列は−

[18,-4,'#',0,8,'#',5]

以下のように変換される必要があります。

[5, 8, "#", 0, -4, "#", 18]

ご覧の通り、数値のみが反転されており、「#」は元のインデックス位置を保持したままになっています。

解決のアプローチ：両ポインタ法

この問題は「両ポインタ（two-pointer）」アプローチを使うことで効率的に解くことができます。まず、startポインタを配列の左端に、endポインタを右端にそれぞれ配置します。

• 走査中にどちらかのポインタが特殊文字を指した場合は、そのインデックスをスキップして次へ進みます。
• 両ポインタが指す要素がどちらも特殊文字でないペアである場合、2つの値を交換します。
• startポインタがendポインタより小さい間、この処理を繰り返します。

実装コード

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

const arr = [18,-4,'#',0,8,'#',5];
const reverseArray = (arr, special) => {
    let start = 0, end = arr.length - 1, temp;
    while(start < end){
        if(arr[start] === special){
            start++;
            continue;
        };
        if(arr[end] === special){
            end--;
            continue;
        };
        temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    };
};
reverseArray(arr, '#');
console.log(arr);

実行結果

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

[
    5, 8, '#', 0, -4, '#', 18
]

計算量について

このアルゴリズムの時間計算量はO(n)、空間計算量はO(1)です。配列をその場で（in-place）書き換えるため、追加のメモリをほとんど必要とせず、大規模な配列に対しても非常に効率的に動作します。特殊文字を含む配列の操作は実務でも応用範囲が広いため、両ポインタ法の考え方と合わせてぜひ覚えておきましょう。