C++でリストを左にK要素だけ回転させる方法

数値のリストが与えられたとき、そのリストを左方向に k 要素分だけ回転させるメソッドを実装する問題を考えてみましょう。

例えば、入力が [5,4,7,8,5,6,8,7,9,2]、k = 2 の場合、出力は [8,5,6,8,7,9,2,5,4,7] となります。先頭の2要素（5と4）が末尾に移動し、残りの要素が前に詰められるイメージです。

解決のアプローチ

この問題は、以下の手順で解くことができます。

• 結果を格納するための配列 ret を定義します。
• n := nums のサイズ（要素数）とします。
• k := k mod n として、k が n 以上の場合に備えます（k が n の倍数なら回転しても元のままになるため）。
• i := k から開始し、i < n の間 i を1ずつ増やしながらループ処理を行います。
  • ret の末尾に nums[i] を挿入します。
• i := 0 から開始し、i < k の間 i を1ずつ増やしながらループ処理を行います。
  • ret の末尾に nums[i] を挿入します。
• ret を返します。

つまり、まず k 番目以降の要素をすべて新しい配列に追加し、その後に先頭から k 個の要素を後ろに追加することで、左回転を実現しています。

C++での実装例

以下のコードを見ると、より理解しやすくなります。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v) {
   cout << "[";
   for (int i = 0; i < v.size(); i++) {
      cout << v[i] << ", ";
   }
   cout << "]" << endl;
}
class Solution {
   public:
   vector<int> solve(vector<int>& nums, int k) {
      vector <int> ret;
      int n = nums.size();
      k %= n;
      for(int i = k; i < n; i++){
         ret.push_back(nums[i]);
      }
      for(int i = 0; i < k; i++){
         ret.push_back(nums[i]);
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {5,4,7,8,5,6,8,7,9,2};
   print_vector(ob.solve(v, 3));
}

入力

{5,4,7,8,5,6,8,7,9,2}, 2

出力

[8, 5, 6, 8, 7, 9, 2, 5, 4, 7]

計算量について

このアルゴリズムの時間計算量は O(n) です。リストの全要素を一度ずつ走査するためです。また、新しい配列 ret を使用しているため、空間計算量も O(n) となります。

補足：in-place での回転

追加メモリを使わずに元の配列を直接変更したい場合は、「全体を反転 → 前半部分を反転 → 後半部分を反転」という三段階の反転テクニックを使うことで、O(1) の追加空間で左回転を実現できます。これは面接などでもよく聞かれる応用テクニックなので、覚えておくと便利です。