配列の k 回転｜コードで実践

配列の k 回転

このレッスンで分かること

スライス を使うと O(n) の 時間 と O(n) の 空間 で完了します

配列の回転 は、要素を 右へ k 回シフト する操作です

難しさは大きく 2 点あります

配列の k 回転とは

整数配列を右へ k 回シフトする 回転 (rotate) を、スライス と 三段反転 の 2 通りで考える。

配列の回転 は、要素を 右へ k 回シフト する操作です。[1, 2, 3, 4, 5] を k = 2 で右回転すると [4, 5, 1, 2, 3] になります。シンプルですが、スライス を使う方法と 三段反転 を使う方法では メモリ使用量 と 配列の捉え方 が大きく違います。本レッスンでは両方の発想を学びます。

「右に k 回す」と「最後の k 個を前に持ってくる」は同じ操作だと気づければ半分は解けたようなもの。

何が難しいのか

難しさは大きく 2 点あります。

k が 配列の長さより大きい ことがある。たとえば長さ 5 の配列を 7 回回転させると、実質 7 % 5 = 2 回回転と同じ。
1 つずつ shift する素朴な実装は O(n * k) で遅い。k が 10^9 のような大きい値で TLE する。

diagram (will load when visible)

図のポイント (テキスト併記)

上図のように、k を n で割った余りを使うだけで一気に効率化できます

上図のように、k を n で割った余りを使うだけで一気に効率化できます。

スライス法 (Python 流)

Python

def rotateArray(nums, k):
    n = len(nums)
    if n == 0:
        return []
    k = k % n
    return nums[-k:] + nums[:-k] if k > 0 else list(nums)

スライス を使うと O(n) の 時間 と O(n) の 空間 で完了します。読みやすく、Python らしい書き方です。

三段反転法 (in-place の定石)

配列を 3 回 reverse するだけで回転できます。発想は意外性がありますが、覚えてしまえば一生使えます。

全体を reverse する
前から k 個を reverse する
残りの n - k 個を reverse する

JavaScript

function rotateArray(nums, k) {
  const n = nums.length;
  if (n === 0) return [];
  k = k % n;
  const arr = nums.slice();
  const reverse = (l, r) => {
    while (l < r) { [arr[l], arr[r]] = [arr[r], arr[l]]; l++; r--; }
  };
  reverse(0, n - 1);
  reverse(0, k - 1);
  reverse(k, n - 1);
  return arr;
}

三段反転は LeetCode の Rotate Array の定石。引数を直接書き換える in-place 実装にすれば O(1) 追加メモリで動く強みがある。ただし上記コードは新しい配列を返す方針のため O(n) 空間を使っている。

`k` の正規化

k = k % n を最初にやらないと、k が巨大なときに O(k) のループを回してしまい間に合いません。また、n == 0 のときは % 0 が ZeroDivisionError になるので、空配列 を先に弾くのが安全です。k = 0 のときは元の配列そのまま、というケースも忘れずに if k == 0 で早期 return しておきます。

計算量

素朴な 1 個ずつ shift は O(n * k)。k = 10^9 で TLE。k % n 正規化 + スライス 連結なら O(n) 時間 / O(n) 空間。三段反転 は引数を直接書き換える実装なら O(n) 時間 / O(1) 空間。新しい配列を返す実装では O(n) 時間 / O(n) 空間。

どちらの解法も 時間 は O(n) ですが、追加メモリ の扱いに違いがあります。上記コードはいずれも新しい配列を返すため空間は O(n) です。in-place で元の配列を直接書き換える実装に変えれば、三段反転は O(1) 追加メモリで動きます。実務では新しい配列を返したいことが多いので、スライス 連結のほうが自然な選択です。一方、巨大配列を mutable に持っていて書き換えが許容できる場合は 三段反転 の in-place 版の出番です。

配列 `回転` の応用例

回転 は リングバッファ、スケジューラ、暗号 (シーザー暗号)、ハッシュ の バケット再配置 などで多用される。覚えておくと多くの場面で再利用できる。

例えば シーザー暗号 で アルファベット 26 文字 を k 個ずらすのは、a..z の配列を k % 26 回転する操作そのものです。円環構造 を扱うときは、まず 配列 + モジュロ を思い浮かべましょう。

よくある間違い

k % n を忘れて、巨大な k で TLE する。
空配列 のチェックを忘れて、% で例外を出す。
元の nums を破壊してしまう。テストでは nums をそのまま参照することはないが、本番ではバグの温床になる。

やってみよう

rotateArray(nums, k) を実装してください。整数配列 nums を k 回 右回転 した新しい配列を返します。k は 0 以上の整数で、配列長より大きい ことがあります。空配列 が来ることもあります。スライス 法でも 三段反転 法でも、どちらでも構いません。

よくある質問

Q. このトピックは実務でどう役立ちますか？

A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。

Q. 計算量はどう求めれば良いですか？

A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。

Q. 覚えるべき定番アルゴリズムは何ですか？

A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。

次のレッスン

次は カッコの妥当性 で、整数配列を右へ k 回シフトする 回転 (rotate) を、スライス と 三段反転 の 2 通りで考えるを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

配列のk回転の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 配列のk回転とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

配列の k 回転