リートコード189 配列の回転

k 回右シフトして O(1) のスペースしか使用しないようにするには、最も簡単な方法は、k 回ループし、そのたびに変数 temp を使用して最後の位置の値を記録し、最後の添え字から添え字 1 までの値を前の要素の値とし、添え字 0 を temp の値とします。 これを k 回実行した後、k 回右シフトしてループが完了します。

しかし、これではタイムアウトしてしまうので、もっと簡単な方法として、k個の数値の配列の前方への右シフトは、それらを1つの部分とみなし、このk個の数値に含まれるすべての数値を1つの部分とみなし、2つの部分を別々に反転させてから配列全体を反転させ、右シフトをk回繰り返した後の配列を得ます。 ライブラリ関数のrotateもこの方法で実装されているようです。

最初のサンプル[1,2,3,4,5,6,7]、k = 3、合計3つの右シフト、最終的な配列は[5,6,7,1,2,3,4]です。

配列の右側から前部分へ移動し、配列の後ろ側をそれぞれ2つの部分に分割して反転を行います：反転の最初の4つの要素で: [4, 3, 2, 1]、反転の最後の3つの要素で: [7, 6, 5]。両方の部分が反転された後、配列は[4, 3, 2, 1, 7, 6, 5]となり、次に配列全体が反転されます：[5, 6, 7, 1, 2, 3, 4]。それで終わり。

kは配列の長さより大きいかもしれませんが、配列を右に動かすたびに原点に戻るので、REVERSE操作ではkと配列の長さのバランスをとる必要があることに注意してください。

class Solution {
public:
 void rotate(vector<int>& nums, int k) {
 int size = nums.size();
 k %= size;
 reverse(nums.begin(), nums.end() - k);
 reverse(nums.end() - k, nums.end());
 reverse(nums.begin(), nums.end());
 }
};