疑问：

swap(a[i][j], a[j][i]);和reverse(a[i], a[i] + n); 这两个std标准库的函数都是空间O（1）的原地操作吗？

回答

是一个非常专业的问题！作为教练，我可以非常肯定地回答你：

是的，这两个操作都是标准的 $O(1)$ 空间复杂度的原地（In-place）操作。

在算法竞赛（OI）和面试中，当我们谈论“空间复杂度”时，通常指的是额外空间复杂度（Auxiliary Space Complexity），即除了存储输入数据本身所需的空间外，算法运行还需要多少额外的内存。

让我们深入 C++ STL 标准库的底层实现来看看为什么。

1. std::swap(a[i][j], a[j][i])

原理分析： std::swap 的作用是交换两个变量的值。对于基础数据类型（如 int），它的内部实现逻辑大概是这样的：

// 简化版实现
void swap(int& a, int& b) {
    int temp = a; // 申请 1 个临时变量的空间
    a = b;
    b = temp;
}

空间复杂度分析：

• 它只申请了一个临时变量 temp。
• 无论你的矩阵 $N$ 是 10 还是 10000，swap 操作永远只需要 1 个整数大小 的额外栈空间。
• 常数空间对应的时间复杂度表示就是 $O(1)$。

2. std::reverse(a[i], a[i] + n)

原理分析： std::reverse 接受两个迭代器（指针）：begin 和 end。它的内部实现本质上就是我们讲过的 **“左右双指针”**技巧。

STL 的大致源码逻辑如下：

// 简化版实现
void reverse(int* first, int* last) {
    // last 指向的是尾后，先回退一格指向最后一个有效元素
    while ((first != last) && (first != --last)) {
        std::iter_swap(first, last); // 交换首尾元素
        ++first; // 左指针右移
    }
}

空间复杂度分析：

• 它只使用了两个指针变量（first 和 last）来标记位置。
• 在交换元素时，调用了 std::iter_swap（本质还是 swap），只消耗 1 个临时变量的空间。
• 它没有申请一个新的数组来存放翻转后的结果，而是直接修改了原数组的内存。
• 因此，它的额外空间消耗也是 $O(1)$。

3. 总结：为什么这个算法是优秀的？

我们回顾一下 $N \times N$ 矩阵旋转的整个过程：

1. 转置：双重循环遍历，内部调用 swap。
   • 额外空间：两个循环变量 $i, j$ + 交换用的 temp = $O(1)$。
2. 翻转行：循环遍历每一行，内部调用 reverse。
   • 额外空间：循环变量 $i$ + reverse 内部的双指针 + 交换用的 temp = $O(1)$。

对比： 如果你开了一个新数组 int b[N][N] 来辅助旋转：

• 你需要 $N^2$ 个整数的额外空间。
• 空间复杂度是 $O(N^2)$。

结论： 利用 swap 和 reverse 的组合解法，完美地利用了 C++ STL 的特性，实现了严格的空间 $O(1)$ 原地修改。这也是为什么这道题在面试和竞赛中如此经典的原因。

放心大胆地用吧！

【参考代码 (C++14 OI Style)】

/**
 * 题目：图像旋转
 * 算法：矩阵转置 + 镜像翻转
 * 时间复杂度：O(N^2)
 * 空间复杂度：O(1) (原地修改)
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
int a[MAXN][MAXN];

int main() {
    // 1. IO 优化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (cin >> n) {
        // 读取矩阵
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cin >> a[i][j];
            }
        }

        // 2. 核心操作步骤 A: 沿主对角线转置矩阵
        // 注意：j 从 i+1 开始，避免重复交换复原
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                swap(a[i][j], a[j][i]);
            }
        }

        // 3. 核心操作步骤 B: 翻转每一行
        // 这一步结合转置，等效于顺时针旋转 90 度
        for (int i = 0; i < n; ++i) {
            // 使用 STL 的 reverse 函数翻转一行
            // a[i] 是第 i 行的首地址，a[i] + n 是第 i 行的尾后地址
            reverse(a[i], a[i] + n);
        }

        // 4. 输出结果
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cout << a[i][j] << (j == n - 1 ? "" : " ");
            }
            cout << "\n";
        }
    }
    return 0;
}

这道题的 测试数据生成器。

这是一个完整的 C++ 数据生成器，专门用于 $N \times N$ 矩阵顺时针旋转 90 度。它包含了标准解答逻辑，并设计了从 $N=1$ 到 $N=1000$ 的各种测试点。

Generator 代码 (gen_rotate.cpp)

请将以下代码保存为 gen_rotate.cpp，编译并运行即可生成 1.in/1.out 到 10.in/10.out。

#include <bits/stdc++.h>
using namespace std;

// ==========================================
// Part 1: 标准解答 (Standard Solution)
// 用于生成 .out 文件
// 逻辑：直接申请一个新矩阵进行旋转，确保结果绝对正确
// ==========================================
void solve_and_write(int n, const vector<vector<int>>& mat, string out_filename) {
    // 构造一个 n x n 的新矩阵
    vector<vector<int>> res(n, vector<int>(n));
    
    // 旋转公式：原图的 (i, j) -> 新图的 (j, n - 1 - i)
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            res[j][n - 1 - i] = mat[i][j];
        }
    }

    // 写入输出文件
    ofstream fout(out_filename);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            fout << res[i][j] << (j == n - 1 ? "" : " ");
        }
        fout << "\n";
    }
    fout.close();
}

// ==========================================
// Part 2: 数据生成器工具
// ==========================================
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int random_int(int L, int R) {
    return uniform_int_distribution<int>(L, R)(rng);
}

// ==========================================
// Part 3: 测试点生成逻辑
// ==========================================
void generate_case(int case_id) {
    int n;
    vector<vector<int>> mat;

    switch (case_id) {
        case 1: // 【样例 1】
            n = 3;
            mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
            break;
            
        case 2: // 【样例 2】
            n = 4;
            mat = {{5, 1, 9, 11}, {2, 4, 8, 10}, {13, 3, 6, 7}, {15, 14, 12, 16}};
            break;
            
        case 3: // 【边界】最小 N=1
            n = 1;
            mat = {{999}};
            break;
            
        case 4: // 【边界】极小 N=2
            n = 2;
            mat = {{10, 20}, {30, 40}};
            break;
            
        case 5: // 【特殊】顺序递增 (方便肉眼检查)
            n = 10;
            mat.resize(n, vector<int>(n));
            {
                int cnt = 0;
                for(int i=0; i<n; i++) 
                    for(int j=0; j<n; j++) 
                        mat[i][j] = ++cnt;
            }
            break;
            
        case 6: // 【常规】中等规模 N=100
            n = 100;
            mat.resize(n, vector<int>(n));
            for(int i=0; i<n; i++) 
                for(int j=0; j<n; j++) 
                    mat[i][j] = random_int(0, 1000);
            break;
            
        case 7: // 【压力】最大规模 N=1000
            n = 1000;
            mat.resize(n, vector<int>(n));
            for(int i=0; i<n; i++) 
                for(int j=0; j<n; j++) 
                    mat[i][j] = random_int(-1000, 1000);
            break;
            
        case 8: // 【压力】最大规模 (奇数)
            n = 999;
            mat.resize(n, vector<int>(n));
            for(int i=0; i<n; i++) 
                for(int j=0; j<n; j++) 
                    mat[i][j] = random_int(-1000, 1000);
            break;
            
        case 9: // 【特殊】全 0 矩阵
            n = 50;
            mat.resize(n, vector<int>(n, 0));
            break;
            
        case 10: // 【特殊】行内元素相同 (条纹状)
            n = 500;
            mat.resize(n, vector<int>(n));
            for(int i=0; i<n; i++) 
                for(int j=0; j<n; j++) 
                    mat[i][j] = i; // 第 i 行全是 i
            break;
            
        default:
            n = 10;
            mat.resize(n, vector<int>(n));
    }

    // ==========================================
    // 文件 I/O 操作
    // ==========================================
    string in_file = to_string(case_id) + ".in";
    string out_file = to_string(case_id) + ".out";

    cout << "Generating Case " << case_id << " (N=" << n << ")..." << endl;

    // 1. 写入 .in
    ofstream fin(in_file);
    fin << n << "\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            fin << mat[i][j] << (j == n - 1 ? "" : " ");
        }
        fin << "\n";
    }
    fin.close();

    // 2. 生成 .out
    solve_and_write(n, mat, out_file);
}

int main() {
    // 生成 1-10 号测试点
    for (int i = 1; i <= 10; ++i) {
        generate_case(i);
    }
    cout << "All test cases generated successfully!" << endl;
    return 0;
}

验证方法

1. 样例检查：
   • 打开 1.in，确认是 $3 \times 3$ 矩阵 1 2 3...。
   • 打开 1.out，确认第一行是 7 4 1（旋转后的结果）。
2. 边界检查：
   • 3.in 应只有一个数字 999，3.out 也应是 999。
3. 特殊模式检查：
   • 10.in 是水平条纹（第0行全是0，第1行全是1）。
   • 10.out 应该变成垂直条纹（第0列全是0，第1列全是1，但因为顺时针旋转，方向可能要注意观察）。具体来说，原图第0行（全是0）变成了新图的最后一列。

祝你的学生 AC 愉快！