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

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].

Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

 

Solution 1: note that line 6 uses k%size. the time complexity of erase is O(n), so the worst total time could be O(n^2)

1 class Solution { 2 public: 3     void rotate(vector
     
      & nums, int k) { 4         int size=nums.size(); 5         int i=0; 6         while (i
     

Solution 2:reverse the previous n-k nums and then reverse the later k nums. Finally reverse all. O(n)

1 2 3 4 5 6 7 

4321567

4 3 2 1 7 6 5

5 6 7 1 2 3 4

1 class Solution { 2 public: 3     void rotate(vector
     
      & nums, int k) { 4         if (nums.empty() || (k %= nums.size()) == 0) return; 5         int n = nums.size(); 6         reverse(nums.begin(), nums.begin() + n - k); 7         reverse(nums.begin() + n - k, nums.end()); 8         reverse(nums.begin(), nums.end()); 9     }10 };