LeetCode 189 Rotate Array

LeetCode

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

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]

Example 2:

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]

Constraints:

1 <= nums.length <= 10<sup>5</sup> -2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1
0 <= 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?

题目大意：

数组原地向右旋转k位

解题思路：

证明如上图，比如[1,2,3,4,5,6,7]中，A = [1,2,3,4], B = [5,6,7]先整体reverse再分别reverse。

解题步骤：

N/A

注意事项：

1. k会大于数组大小，所以取mod
2. Python中reverse一个sublist，方法先取sublist再倒转

Python代码：

def 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)