配列の k 回転

1 個ずつずらすと、k が大きいときに終わらない

「右に 1 つずらす」を k 回繰り返せば答えは出ます。長さ 5 の配列を 2 回まわすだけなら、それで十分です。ところが k に 10^9 が来た瞬間、この素朴な実装は O(n * k) になって帰ってきません。

先に気づくべきなのは、長さ 5 の配列を 7 回まわした結果が、2 回まわした結果とまったく同じだという点です。1 周ぶんの回転は、何もしていないのと変わりません。だから k はそのまま使わず、n で割った余りに畳んでから使います。

曜日を 100 日ぶん進めるとき、100 回ループを回す人はいません。配列の回転も同じ発想です。

「右に k 回す」を、完成形から見直す

回転を「1 つずらす操作の繰り返し」と捉えている限り、ループの外へ出られません。先に完成形を見てしまうのが早道です。

[1, 2, 3, 4, 5] を 2 回まわすと [4, 5, 1, 2, 3] になります。並びをよく見てください。[4, 5] も [1, 2, 3] も、元の順序のまま崩れずに残っています。動いたのは、この 2 つのかたまりの前後関係だけです。

ここまで言い換えられれば、何回まわすかという話は消えて、どこで切るかという話になります。切る位置を決めるのに使うのが、さきほどの余りです。

なお、切り出して繋ぎ直すやり方は新しい配列を 1 本ぶん作るので、メモリを O(n) 使います。追加のメモリをほとんど使わずに済ませたい場面では、reverse を何度か組み合わせて同じ並びに持っていく手も知られています。ただしそちらは元の配列をその場で書き換える前提です。

どちらを選ぶかは速さではなく、元の配列を壊してよいかで決まります。今回は残す必要があるので、新しい配列を返す側で考えてください。実務でも、呼び出し元が渡した配列が知らないうちに書き換わっているのは、追いにくいバグの代表格です。

n が 0 のときだけ、別の壊れ方をする

k % n は便利ですが、n が 0 だと割り算そのものが例外になります。空配列は「何回まわしても空配列」なので、余りを取る前に片付けておくのが安全です。k が 0 のときも、余計な処理を挟まずそのまま返せます。

境界が 2 つあるときは、どちらを先に弾くかで書きやすさが変わります。空配列を先に返してしまえば、その後の行では長さが 1 以上であることを前提にできるので、条件がひとつ減ります。

テストで確かめるべきは、k が長さちょうどのとき、長さより大きいとき、0 のとき、そして要素が 1 個だけのときです。この 4 つが通れば、真ん中あたりの値はまず外しません。

やってみよう

rotateArray(nums, k) を実装してください。整数配列 nums を右へ k 回まわした新しい配列を返します。k は 0 以上の整数で、nums の長さより大きいことがあります。空配列が渡ってくることもあります。元の nums は書き換えないでください。

1. 関数 rotateArray(nums, k) を実装し、回転後の新しい配列を返す
2. k % n で正規化し、k が nums.length より大きくても効率よく動くこと
3. 元の nums を破壊しない (新しい配列を返す)