> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/array_and_numbers/rotate-array.md).

# 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).