# 189.Rotate Array

**189.Rotate Array**

难度:Easy

> 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

```
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
```

说明: 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。 要求使用空间复杂度为 O(1) 的原地算法

方法：

1. 原地操作

```
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k=k%n;
        reverse(nums,0,n-k-1);
        reverse(nums,n-k,n-1);
        reverse(nums,0,n-1);
    }
private:
    void reverse(vector<int>& nums,int low, int high) {
        while(low <= high){
            swap(nums[low], nums[high]);
            low++;
            high--;
        }
    }
};
```

时间复杂度O(n),空间复杂度O(1)。 数组(A,B)进行对称操作后，为(B对称，A对称)，然后将A,B分别对称即可的到(B,A)，题目中以n-k为边界分别对称即可。 实际上，两个数列进行对称操作后，合并之后的数列再进行对称操作，即可完成该题目中数组旋转。

1. 队列操作

```
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        deque<int>tmp(nums.begin(),nums.end());
        k=k%nums.size();
        while(k--)
        {
            int t=tmp[tmp.size()-1];
            tmp.pop_back();
            tmp.push_front(t);
        }
        for(int i=0;i<tmp.size();i++)
            nums[i]=tmp[i];
        
    }
};
```

时间复杂度O(n),空间复杂度O(n)。

1. 循环交换(原地)

```
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int len=nums.size();
        k=k%len;
        if(!k) return;
        int t=len-k;
        int tmp;
        while(k--){
            tmp=nums[len-1];
        for(int i=len-1;i>0;i--)
        {
            nums[i]=nums[i-1];
        }
            nums[0]=tmp;
        }
        
    }
};
```

时间复杂度O(kn),空间复杂度O(1),当k->n时，有O(n^2)的复杂度。会显示超时。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dfine.gitbook.io/leetcode/189.rotate_array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.