Rotate Array

https://leetcode.com/problems/rotate-array/description/

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.

[show hint]

Related problem: Reverse Words in a String II

Thoughts

右移k次相当于走到i+k处，由于超出array size, 相当于循环走，在相对位置0的位置最后落脚(i+k)%n。左移相当于i-k处，这时不能直接取模，值可能是负的，要加n取模，相当于相对位置n-1的位置最后落脚(n+i-k)%n。以上需要额外O(N)空间复杂度。

右移相当于把i移到i + k - N位置上，全部翻转i -> N-i位置，再对K内翻转N-i->k-(N - i)即i + k -N。相当于把前面K个翻转移到最后，后面N-K个翻转放到前面。

Code

/*
 * @lc app=leetcode id=189 lang=cpp
 *
 * [189] Rotate Array
 */
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

Analysis

时间O(N), 空间O(1).