アルゴリズム体操５

Rotate Array

##説明

整数型の配列と整数N(回転数)の二つの引数が渡されたとき、配列の要素をN回(マイナスは左へ、プラスは右へ)
回転させた配列にしよう。

##例
以下の配列が渡されたとしよう。

もし、回転数Nが−１の時は、全ての要素が左側へ一つずつずれる。

また、もし回転数Nが２の場合は、全ての要素が右側へ一つずつ二回ずれる。

Try It Yourself (Brute Force)

この問題でまず私が最初に思い浮かんだ、力任せアルゴリズムは回転後に
必ず二つの左側、右側の部分配列が現れるので、その二つの配列を作る。
(例のN＝2のケースでは、left_sub_array = {9 , 40}で、right_sub_array = {1, 10, 20, 0, 59, 86, 32, 11})
そして、左側と右側の部分配列に保存してある回転後の要素を元の配列に順番に更新していく。
もし、Nがマイナスの時は左回転を右回転のアルゴリズムに適用できる様にする。
###実行時間(Runtime Complexity) O(n)
###空間計算量(Memory Complexity) O(n)
###実装

###TEST

###OUTPUT

###見直し
要素の順序を入れ替えていくには、全ての要素の位置を並び替える必要があるため、実行時間O(n)が限界である。
ただ、空間計算量はO(1)にすることができる。つまりは渡されたデータ構造のみを使う。

##最適化: Memory Complexity O(n) -> O(1)

1. 元の配列の要素を反転します。
2. 0からN-1までの要素を反転します。
3. NからLength-1までの要素を反転します

###例
先の例と同じ配列が渡されたとする。また、回転数はN=2とする。

1. まず、元の配列の要素全てを反転させる。
   
2. それから、index 0 から N-1(2 - 1 = 1)までの要素を反転させる。
   
3. 最後にN(2)から配列の末尾までの要素を反転させる。
   
   これで、空間計算量が定数O(1)で最適化できる。
   ###実装
   

###OUTPUT (TESTのコードは同じ)