LeetCode 189. Rotate Array[Easy]
题目地址:https://leetcode.com/problems/rotate-array/
题解地址:https://leetcode.com/articles/rotate-array/
题目
Given an array, rotate the array to the right by k steps, where k is non-negative.
Follow up:
- Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
- Could you do it in-place with O(1) extra space?
Example 1:
1 | Input: nums = [1,2,3,4,5,6,7], k = 3 |
Example 2:
1 | Input: nums = [-1,-100,3,99], k = 2 |
Constraints:
1 <= nums.length <= 2 * 10^4
- It’s guaranteed that
nums[i]
fits in a 32 bit-signed integer. k >= 0
解法1:蛮力法
思路
一次向右移动 1 位,移动 k 次。
代码
略
解法2:使用额外数组
思路
使用和原数组大小相同的额外数组,直接把原数组元素放置到新数组对应位置上。
代码
略
解法3:循环赋值
思路
从第一个元素开始依次向后移动,每次都先把下一个元素缓存起来,这样最终会循环到最初的位置。
代码
解法4:三次翻转
思路
整体翻转一次。
把前 k 个翻转一下。
把后 n-k 个翻转一下。