JavaScriptで配列を回転させる方法：追加メモリ不要の実装テクニック

JavaScriptで、配列と数値 n を受け取る関数を作成することを考えます。

この関数は、配列を n 個ぶんだけ回転させるものです。つまり、先頭から n 個の要素を取り出し、それらを配列の末尾へ移動します。

ただし、ここで求められる唯一の条件は、余分なメモリ領域を使用しないことです。

具体例

たとえば、入力配列が次のようになっているとします。

const arr = [12, 6, 43, 5, 7, 2, 5];

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

const output = [5, 7, 2, 5, 12, 6, 43];

先頭の「12」「6」「43」の3要素が末尾へ移動し、残りの要素が前に詰められているのがわかります。

実装コード

以下が実際のコード例です。

const arr = [12, 6, 43, 5, 7, 2, 5];
const num = 5;
const rotateByOne = arr => {
    for(let i = 0; i < arr.length-1; i++){
        temp = arr[i];
        arr[i] = arr[i+1];
        arr[i+1] = temp;
    };
}
Array.prototype.rotateBy = function(n){
    const { length: l } = this;
    if(n >= l){
        return;
    };
    for(let i = 0; i < n; i++){
        rotateByOne(this);
    };
};
arr.rotateBy(num);
console.log(arr);

出力結果

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

[
    2, 5, 12, 6,
   43, 5,  7
]

コードの解説

このアプローチの中心となるのは rotateByOne 関数です。この関数は、隣接する2つの要素を順番に入れ替えていくことで、配列全体を1つぶん左へシフトします。

続いて、Array.prototype.rotateBy メソッドを定義しています。このメソッドは、指定された回数 n だけ rotateByOne を呼び出すことで、n 要素ぶんの回転を実現します。また、n が配列の長さ以上の場合は回転しても元と同じ並びになるため、何もせずに処理を終了するガードが入っています。

隣接要素のスワップだけで完結するため、新しい配列や一時的なバッファは一切不要です。そのため空間計算量は O(1) となり、「追加メモリを使わない」という条件を満たしています。

一方で注意点もあります。1要素の回転に配列全体を走査するため、時間計算量は O(n × l)(l は配列の長さ)になります。大きな配列を大量に回転させるケースでは、パフォーマンスへの影響を考慮しておくとよいでしょう。