<div>
Given an array, rotate the array to the right by k steps, where k is non-negative.
Example 1:
<pre>Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4] </pre>
Example 2:
<pre>Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100] </pre>
Constraints:
1 <= nums.length <= 10<sup>5</sup>-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 10 <= k <= 10<sup>5</sup>
Follow up:
- Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
- Could you do it in-place with
O(1)extra space?
</div>
题目大意：
数组原地向右旋转k位
解题思路：
证明如上图，比如[1,2,3,4,5,6,7]中，A = [1,2,3,4], B = [5,6,7]先整体reverse再分别reverse。
解题步骤：
N/A
注意事项：
- k会大于数组大小，所以取mod
- Python中reverse一个sublist，方法先取sublist再倒转
Python代码：
1
2
3
4
5def rotate(self, nums: List[int], k: int) -> None:
k = k % len(nums) # remember
nums[:] = nums[::-1]
nums[:k] = nums[:k][::-1] # remember how to reverse sublist
nums[k:] = nums[k:][::-1]
算法分析：
时间复杂度为O(n)，空间复杂度O(1)
