0189. Rotate Array
==================
题目信息
--------
:题号: 0189. 轮转数组
:难度: Medium
:主题: 数组、下标映射、原地反转
:原题: `LeetCode 0189 `_
:重点: 从元素目标下标推导分段置换,再用三次反转删除辅助数组并保持两段内部顺序
题目重述
--------
给定整数数组 ``nums`` 和非负整数 ``k``,将数组整体向右轮转 ``k`` 步。每一步都把最后
一个元素移动到最前面,要求直接修改输入数组。
进阶目标是使用 ``O(1)`` 额外空间。
自建示例
--------
.. code-block:: text
输入:nums = [1,2,3,4,5,6,7], k = 3
修改后:[5,6,7,1,2,3,4]
.. code-block:: text
输入:nums = [-1,-100,3,99], k = 6
修改后:[3,99,-1,-100]
6 mod 4 = 2,只需右移两步。
.. code-block:: text
输入:nums = [8], k = 100
修改后:[8]
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
private:
void extraBuffer(std::vector& nums, int k) {
int size = static_cast(nums.size());
if (size == 0) {
return;
}
int shift = k % size;
std::vector rotated(size);
for (int index = 0; index < size; ++index) {
rotated[(index + shift) % size] = nums[index];
}
nums = std::move(rotated);
}
void threeReversals(std::vector& nums, int k) {
int size = static_cast(nums.size());
if (size <= 1) {
return;
}
int shift = k % size;
if (shift == 0) {
return;
}
std::reverse(nums.begin(), nums.end());
std::reverse(nums.begin(), nums.begin() + shift);
std::reverse(nums.begin() + shift, nums.end());
}
public:
void rotate(std::vector& nums, int k) {
threeReversals(nums, k);
}
};
题解
----
逐步轮转重复搬移前缀
~~~~~~~~~~~~~~~~~~~~
完全模拟定义时,每一步取出末元素,再把其余 ``n-1`` 个元素右移,为新首元素腾位置。
一次需要 ``O(n)`` 搬移,执行 ``k`` 次最坏为 ``O(nk)``;同一元素会被来回移动很多次。
轮转 ``n`` 步会回到原数组,所以先令 ``shift = k % n``。这不只是性能优化,也把所有
输入统一到 ``0..n-1`` 的实际位移;``shift = 0`` 时可以直接返回。代码在取模前处理空
数组,避免除以零,虽然题目正式输入通常保证非空。
目标下标给出线性基线
~~~~~~~~~~~~~~~~~~~~
右移 ``shift`` 后,原下标 ``index`` 的元素目标位置唯一确定:
.. code-block:: text
destination = (index + shift) % n
``extraBuffer`` 创建同长数组,按该映射把每个元素直接写到最终位置。它将时间降为
``O(n)``,不会重复移动;但映射可能形成多个置换环,直接覆盖原数组会破坏尚未读取的值,
所以基线使用 ``O(n)`` 辅助空间。
题目要求继续删除这块缓冲区。与其逐元素追踪置换环,可以从目标结果的两段结构出发。
右旋是两段交换
~~~~~~~~~~~~~~
将原数组按末尾 ``shift`` 个元素分成:
.. code-block:: text
A = nums[0 .. n-shift)
B = nums[n-shift .. n)
右旋目标是 ``B + A``,而且 A、B 各自的内部顺序都必须保持。整体反转满足:
.. code-block:: text
reverse(A + B) = reverse(B) + reverse(A)
这已经把 B 移到前面、A 移到后面,只是两段内部都颠倒。再分别反转前 ``shift`` 项和其余
项,就得到:
.. code-block:: text
reverse(reverse(B)) + reverse(reverse(A)) = B + A
三次反转全部在原数组上交换对称位置,不需要保存被覆盖的完整副本。
具体状态走读
~~~~~~~~~~~~
对 ``[1,2,3,4,5,6,7]``、``shift = 3``:
.. code-block:: text
原数组: [1,2,3,4,5,6,7] A=[1,2,3,4], B=[5,6,7]
整体反转: [7,6,5,4,3,2,1] reverse(B)+reverse(A)
反转前 3 项: [5,6,7,4,3,2,1] B+reverse(A)
反转剩余部分: [5,6,7,1,2,3,4] B+A
C++ ``std::reverse(first,last)`` 使用左闭右开区间,所以三次调用分别覆盖
``[0,n)``、``[0,shift)``、``[shift,n)``,两段边界没有遗漏或重叠。若把第二次反转的
长度误写为 ``n-shift``,恢复的会是错误分段,方向也可能变成左旋。
元素与边界不变量
~~~~~~~~~~~~~~~~
每次区间反转都把两端元素交换后向中间收缩;已离开活动区间的对称位置已经处于该次反转
的最终位置,不再修改。奇数长度区间的中点无需移动,重复值也不影响位置置换。
``size <= 1`` 时任何轮转都不改变数组;``shift = 0`` 时 A 是完整数组、B 为空,目标仍为
A。主解显式提前返回,避免构造空的前段反转边界。
方案选择与复杂度
~~~~~~~~~~~~~~~~
逐步搬移最坏时间 ``O(nk)``;辅助数组按目标下标直接放置,时间 ``O(n)``、空间
``O(n)``,清楚展示了轮转置换。三次反转保持同样的 ``O(n)`` 时间,只使用常数个迭代器和
交换临时值,额外空间 ``O(1)``,因此 ``threeReversals`` 是主解。