Rotate an Array

Leetcode #189

Description:

Rotate an array of n elements to the right by k steps.

Try not to use extra space.

Example:

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Idea:

Method 1: use extra space of array is easy

Method 2: Reverse

1. Reverse all
2. Reverse first k
3. Reverse last n-k

Method 3: Using Cyclic Replacements (太复杂了！)

Let arr[] be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

每组里面的单个挪。
a)    Elements are first moved in first set – (See below diagram for this movement)
          arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}

b)    Then in second set.
          arr[] after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}

c)    Finally in third set.
          arr[] after this step --> {4 5 6 7 8 9 10 11 12 1 2 3}

Code:

Use method 2

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