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());
}
};
``````