Knowledge Framework

Appearance

On this page

1. 题解 ​

js
/**

* @param {number[]} nums

* @param {number} k

* @return {void} Do not return anything, modify nums in-place instead.

*/

var rotate = function(nums, k) {
	const swap = ({nums, left, right}) => {
		while (left < right) {
			var temp = nums[left]
			nums[left] = nums[right]
			nums[right] = temp
			left++
			right--
		}
	}
	var realK = k % nums.length
	swap({nums, left: 0, right: nums.length - 1})
	swap({nums, left: 0, right: realK - 1})
	swap({nums, left: realK, right: nums.length - 1})
};

2. 问题分析 ​

原因：

  1. 两次翻转，在区间内顺序与原一致
  2. 边界值左右两个值，意味着头和尾。一边头，一边尾。
  3. 根据边界值，等价于右轮/左轮

注意：

  • 留意原位置边界值左右会变成首尾，一般以 k 位为边界值。
  • 留意正数/倒数 k 位，轮转 k 位到首/尾。
  • 先总翻转、先分区翻转，这个顺序不重要。后续只要记得一套解题思路即可，这样就不会乱。

翻转顺序不重要，重要的是原位置边界定的位置：

  1. 先总翻转，再分区翻转，此时的【边界】用 k，是右翻转。 如果用 n - k 是左翻转
  2. 先分区翻转，再总翻转，此时的【边界】用 k，是左翻转。这个也容易理解，先分区翻转，此时的 k 等同于 【先总翻转，在分区翻转时的 n - k 】，因为先总翻转导致原本的 k 变成了 n - k, 即 k => n - k
js
1 2 3 4 5 6 7 8 原

k = 2

- 先分区翻转，再总翻转，k = 2
1 2|3 4 5 6 7 8 原
2 1|8 7 6 5 4 3 k = 2 的分区翻转
3 4 5 6 7 8|1 2 总翻转

1 2 3 4 5 6 7 8 原，对比就可以看出总翻转后左轮转了 k = 2
3 4 5 6 7 8 1 2 操作后

- 先总翻转，再分区翻转
1 2 3 4 5 6 7 8 原
8 7|6 5 4 3 2 1 总翻转 k = 2
7 8|1 2 3 4 5 6 k = 2 的分区翻转

1 2 3 4 5 6 7 8 原，对比就可以看出总翻转后右轮转了 k = 2
7 8 1 2 3 4 5 6 操作后

原因是先总翻转后的 k = 2，实际对应的位置是翻转前的 n - k = 8 - 2 = 6 位置
所以，翻转顺序不重要，重要的是【原位置】边界的位置。

3. 结论 ​

为了保证逻辑清晰， 不用在边界上的计算有思考负担，我们遵守

  • 先分区翻转，再总翻转

这样 k 就是正序顺序，不用考虑翻转后的。

  • 左翻转，使用 k。
  • 右翻转，使用 n - k。
JavaScript
- 左翻转 k = 2
1 2|3 4 5 6 7 8 原
2 1|8 7 6 5 4 3 k = 2 的分区翻转
3 4 5 6 7 8|1 2 总翻转

1 2 3 4 5 6 7 8 原，对比就可以看出总翻转后左轮转了 2
3 4 5 6 7 8 1 2 操作后


- 右翻转 k = n - k = 8 - 2 = 6
1 2 3 4 5 6|7 8 原
6 5 4 3 2 1|8 7 k = 6 的分区翻转
7 8|1 2 3 4 5 6 总翻转

1 2 3 4 5 6 7 8 原，对比就可以看出总翻转后右轮转了 2
7 8 1 2 3 4 5 6 操作后