yicong@algo: ~/code/05-array/0189-rotate-array.cpp

yicong@algo:~/code/05-array$ cat 0189-rotate-array.cpp

189. 轮转数组

中等 普通数组 题目 ↗ 源码 ↗

// 思路

右旋 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;
}