problems/0189.旋转数组.md · programmercarl/leetcode-master（代码随想录出品）

<a href="https://www.programmercarl.com/xunlian/xunlianying.html" target="_blank">
 <img src="../pics/训练营.png" width="1000"/>
</a>
<a href="./qita/join.md">参与本项目</a>，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！

# 189. 旋转数组

[力扣题目链接](https://leetcode.cn/problems/rotate-array/)

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

进阶：

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

示例 1:

* 输入: nums = [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:
* 输入：nums = [-1,-100,3,99], k = 2
* 输出：[3,99,-1,-100]
* 解释:
向右旋转 1 步: [99,-1,-100,3]。
向右旋转 2 步: [3,99,-1,-100]。

## 思路

这道题目在字符串里其实很常见，我把字符串反转相关的题目列一下：

* [字符串：力扣541.反转字符串II](https://programmercarl.com/0541.反转字符串II.html)
* [字符串：力扣151.翻转字符串里的单词](https://programmercarl.com/0151.翻转字符串里的单词.html)
* [字符串：剑指Offer58-II.左旋转字符串](https://programmercarl.com/剑指Offer58-II.左旋转字符串.html)

本题其实和[字符串：剑指Offer58-II.左旋转字符串](https://programmercarl.com/剑指Offer58-II.左旋转字符串.html)就非常像了，剑指offer上左旋转，本题是右旋转。

注意题目要求是**要求使用空间复杂度为 O(1) 的 原地 算法**

那么我来提供一种旋转的方式哈。

在[字符串：剑指Offer58-II.左旋转字符串](https://programmercarl.com/剑指Offer58-II.左旋转字符串.html)中，我们提到，如下步骤就可以坐旋转字符串：

1. 反转区间为前n的子串
2. 反转区间为n到末尾的子串
3. 反转整个字符串

本题是右旋转，其实就是反转的顺序改动一下，优先反转整个字符串，步骤如下：

1. 反转整个字符串
2. 反转区间为前k的子串
3. 反转区间为k到末尾的子串

**需要注意的是，本题还有一个小陷阱，题目输入中，如果k大于nums.size了应该怎么办？**

举个例子，比较容易想，

例如，1,2,3,4,5,6,7  如果右移动15次的话，是 7 1 2 3 4 5 6  。

所以其实就是右移 k % nums.size() 次，即：15 % 7 = 1

C++代码如下：

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

}
};
```

## 其他语言版本

### Java

```java
class Solution {
 private void reverse(int[] nums, int start, int end) {
 for (int i = start, j = end; i < j; i++, j--) {
 int temp = nums[j];
 nums[j] = nums[i];
 nums[i] = temp;
 }
 }
 public void rotate(int[] nums, int k) {
 int n = nums.length;
 k %= n;
 reverse(nums, 0, n - 1);
 reverse(nums, 0, k - 1);
 reverse(nums, k, n - 1);
 }
}
```

### Python

方法一：局部翻转 + 整体翻转
```python
class Solution:
 def rotate(self, A: List[int], k: int) -> None:
 def reverse(i, j):
 while i < j:
 A[i], A[j] = A[j], A[i]
 i += 1
 j -= 1
 n = len(A)
 k %= n
 reverse(0, n - 1)
 reverse(0, k - 1)
 reverse(k, n - 1)
```

方法二：利用余数

```python 
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        copy = nums[:]

for i in range(len(nums)):
            nums[(i + k) % len(nums)] = copy[i]
        
        return nums

# 备注：这个方法会导致空间复杂度变成 O(n) 因为我们要创建一个 copy 数组。但是不失为一种思路。
```

### Go

```go
func rotate(nums []int, k int) {
 l:=len(nums)
 index:=l-k%l
 reverse(nums)
 reverse(nums[:l-index])
 reverse(nums[l-index:])
}
func reverse(nums []int){
 l:=len(nums)
 for i:=0;i<l/2;i++{
 nums[i],nums[l-1-i]=nums[l-1-i],nums[i]
 }
}
```

### JavaScript

```js
var rotate = function (nums, k) {
 function reverse(nums, i, j) {
 while (i < j) {
 [nums[i],nums[j]] = [nums[j],nums[i]]; // 解构赋值
 i++;
 j--;
 }
 }
 let n = nums.length;
 k %= n;
 if (k) {
 reverse(nums, 0, n - 1);
 reverse(nums, 0, k - 1);
 reverse(nums, k, n - 1);
 }
};
```

### TypeScript

```typescript
function rotate(nums: number[], k: number): void {
 const length: number = nums.length;
 k %= length;
 reverseByRange(nums, 0, length - 1);
 reverseByRange(nums, 0, k - 1);
 reverseByRange(nums, k, length - 1);
};
function reverseByRange(nums: number[], left: number, right: number): void {
 while (left < right) {
 const temp = nums[left];
 nums[left] = nums[right];
 nums[right] = temp;
 left++;
 right--;
 }
}
```

programmercarl/leetcode-master（代码随想录出品）

简介

发行版

贡献者

近期动态

programmercarl/leetcode-master（代码随想录出品） .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

programmercarl/leetcode-master（代码随想录出品）