1 Star 0 Fork 0

李毅聪 / algorithm-practice

加入 Gitee
与超过 1400万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
0189-rotate-array.cpp 5.76 KB
一键复制 编辑 原始数据 按行查看 历史
李毅聪 提交于 2026-11-17 23:29 +08:00 . 0189 轮转数组:三次反转 O(n)/O(1)
// 力扣 189. 轮转数组(中等)Hot100
// https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-100-liked
//
// 思路:
// 右旋 k 位,等价于把数组切成 [前 n-k 个] [后 k 个] 两段,然后把这两段整体交换。
// 而"交换两段"可以用三次反转实现,因为反转是自逆操作:
// ① 整体反转 [1,2,3,4,5,6,7] → [7,6,5,4,3,2,1]
// ② 反转前 k 个 → [5,6,7,4,3,2,1]
// ③ 反转后 n-k 个 → [5,6,7,1,2,3,4] ← 答案
// 为什么成立:整体反转把"后 k 个"甩到了前面、但内部顺序被打乱了;
// 再分别把这两段各自反转一次,各自的内部顺序就恢复了,位置交换保留下来。
//
// 版本一(你的写法):每次把最后一个搬到队首、再弹掉尾巴,重复 k 次。
// 逻辑非常直观,但 nums.insert(nums.begin(), ...) 要把所有元素整体后移一格,
// 是 O(n) 的,外面再套 k 次循环 → O(n·k)。
// 版本二:三次反转,O(n) 时间 / O(1) 空间,力扣进阶要求的标准答案。
//
// 时间复杂度:
// 版本一:O(n·k)。实测 n = 10万、k = 10万 需要约 780 ms。
// 版本二:O(n)。三次 reverse 各扫一遍,总共 1.5n 次交换。
// 空间复杂度:
// 版本一:O(n),vector 自己的缓冲区(每次 insert 都可能触发扩容搬迁)
// 版本二:O(1),只用了几个下标,原地交换
//
// 易错点:
// 1. k 必须先对 n 取模。k 可能比 n 大:n=2、k=3 时右旋 3 位等于右旋 1 位。
// 版本二里尤其致命——nums.begin() + k 超出 end() 是未定义行为。
// 2. 取模前要判 n == 0,否则 n 为 0 时 k % n 是除零,直接崩溃。
// 3. 三次反转的边界是左闭右开:reverse(begin, begin + k) 反转的是下标 [0, k),
// 不包含下标 k。三次的边界必须对齐,否则答案整体偏移。
// 4. 三次反转的顺序不能乱,必须是 整体 → 前 k → 后 n-k。
// 5. 版本一里 nums.insert(nums.begin(), nums.back()) 是"自引用插入":
// nums.back() 返回的是指向容器内部的引用,而 insert 可能触发扩容(重新分配内存)。
// libstdc++ 的实现顺序是"先构造新元素、再搬旧元素",实测是安全的,
// 但不同标准库不保证。先写 int last = nums.back(); 成本为零,建议这么写。
// 6. 版本一里 nums.back() 在空数组上是未定义行为。题目保证 n >= 1,但通用函数要防。
//
// 面试口述要点:
// 1. 先给朴素解:每次搬一个,k 次,O(n·k),说明为什么会慢(insert 到队首是 O(n));
// 2. 再给额外数组解:新开一个数组按下标映射放好再拷回,O(n) 时间 / O(n) 空间;
// 3. 正解三次反转:O(n) 时间 / O(1) 空间,讲清"右旋 k 位 = 交换前后两段"这个等价;
// 4. 还可以提环状替换(下标 i 的元素换到 (i+k) % n,按 gcd(n,k) 分组循环),
// 同样 O(n)/O(1),但下标推导容易绕晕,面试时不如三次反转好讲;
// 5. 工程上算法库已经有 std::rotate,一行就能做:
// rotate(nums.begin(), nums.begin() + (n - k), nums.end());
// 但被问"怎么实现"时还是要答得出上面两种。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// ================================================================
// 版本一:每次把末尾搬到队首,重复 k 次(你的写法),O(n·k)
// ================================================================
void rotate(vector<int>& nums, int k) {
for (int i = 0; i < k; i++) {
nums.insert(nums.begin() , nums.back());
nums.pop_back();
}
}
// ================================================================
// 版本二:三次反转,O(n) 时间 / O(1) 空间
// ================================================================
void rotate_v2(vector<int>& nums, int k) {
int n = (int)nums.size();
if (n == 0) {
return; // 空数组直接返回,也避免下面的 % 除零
}
k %= n; // k 可能比 n 大,先规约
if (k == 0) {
return; // 转一整圈等于没动,省三次 reverse
}
// ① 整体反转:[1,2,3,4,5,6,7] → [7,6,5,4,3,2,1]
reverse(nums.begin(), nums.end());
// ② 反转前 k 个:[7,6,5,4,3,2,1] → [5,6,7,4,3,2,1]
// 注意是左闭右开,反转下标 [0, k)
reverse(nums.begin(), nums.begin() + k);
// ③ 反转后 n-k 个:[5,6,7,4,3,2,1] → [5,6,7,1,2,3,4]
reverse(nums.begin() + k, nums.end());
}
};
// 本地测试:输入 n k,然后 n 个整数;输出向右轮转 k 位后的整个数组
// 同时跑两个版本并比对结果,方便验证优化版和原版等价
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
if (!(cin >> n >> k)) return 0;
vector<int> nums(n);
for (int& x : nums) cin >> x;
vector<int> copy = nums; // 版本二会原地改数组,各用一份
Solution().rotate(nums, k);
Solution().rotate_v2(copy, k);
if (nums != copy) {
cout << "MISMATCH\nv1:";
for (size_t i = 0; i < nums.size(); ++i) cout << ' ' << nums[i];
cout << "\nv2:";
for (size_t i = 0; i < copy.size(); ++i) cout << ' ' << copy[i];
cout << '\n';
return 0;
}
if (nums.empty()) {
cout << "none\n";
} else {
for (size_t i = 0; i < nums.size(); ++i)
cout << nums[i] << (i + 1 == nums.size() ? '\n' : ' ');
}
return 0;
}
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/yicongl1/algorithm-practice.git
git@gitee.com:yicongl1/algorithm-practice.git
yicongl1
algorithm-practice
algorithm-practice
main

搜索帮助