矩陣順時針旋轉 90°：創新工場筆試題 C++ 實現與通用解法

矩陣順時針旋轉 90°：創新工場筆試題 C++ 實現與通用解法

經典面試/筆試題：給定 N×N 矩陣，原地或輔助空間實現順時針/逆時針 90°、180° 旋轉及轉置。本文提供清晰的索引映射規律、完整 C++ 代碼、時空複雜度分析及原地旋轉進階方案。

一、索引映射規律（N×N 矩陣，0-based 索引）

二、輔助空間 O(N²) 完整實現

#include <iostream>
#include <vector>
using namespace std;

using Matrix = vector<vector<int>>;

Matrix rotate90Clockwise(const Matrix& src) {
    int n = src.size();
    Matrix dst(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            dst[i][j] = src[n - 1 - j][i];
    return dst;
}

Matrix rotate90CounterClockwise(const Matrix& src) {
    int n = src.size();
    Matrix dst(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            dst[i][j] = src[j][n - 1 - i];
    return dst;
}

Matrix rotate180(const Matrix& src) {
    int n = src.size();
    Matrix dst(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            dst[i][j] = src[n - 1 - i][n - 1 - j];
    return dst;
}

Matrix transpose(const Matrix& src) {
    int n = src.size();
    Matrix dst(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            dst[i][j] = src[j][i];
    return dst;
}

void printMatrix(const Matrix& m) {
    for (const auto& row : m) {
        for (int v : row) cout << v << '\t';
        cout << '\n';
    }
}

int main() {
    Matrix mat = {{1,2,3}, {4,5,6}, {7,8,9}};
    cout << "Original:\n"; printMatrix(mat);
    cout << "\nClockwise 90:\n"; printMatrix(rotate90Clockwise(mat));
    cout << "\nCounterClockwise 90:\n"; printMatrix(rotate90CounterClockwise(mat));
    cout << "\n180:\n"; printMatrix(rotate180(mat));
    cout << "\nTranspose:\n"; printMatrix(transpose(mat));
    return 0;
}

三、輸出示例

Original:
1	2	3	
4	5	6	
7	8	9	

Clockwise 90:
7	4	1	
8	5	2	
9	6	3	

CounterClockwise 90:
3	6	9	
2	5	8	
1	4	7	

180:
9	8	7	
6	5	4	
3	2	1	

Transpose:
1	4	7	
2	5	8	
3	6	9	

四、進階：原地旋轉 O(1) 空間（順時針 90°）

分層旋轉，每層四邊元素四向循環交換。

void rotate90InPlace(Matrix& mat) {
    int n = mat.size();
    for (int layer = 0; layer < n / 2; ++layer) {
        int first = layer;
        int last = n - 1 - layer;
        for (int i = first; i < last; ++i) {
            int offset = i - first;
            int top = mat[first][i];  // 保存上邊
            // 左 → 上
            mat[first][i] = mat[last - offset][first];
            // 下 → 左
            mat[last - offset][first] = mat[last][last - offset];
            // 右 → 下
            mat[last][last - offset] = mat[i][last];
            // 上(保存) → 右
            mat[i][last] = top;
        }
    }
}

五、複雜度總結

六、非方陣（M×N）旋轉擴展

• 順時針 90°：M×N → N×M，dst[j][M-1-i] = src[i][j]
• 需動態分配目標矩陣，原地旋轉不可行（維度改變）。

七、避坑指南

1. 索引映射公式務必在紙上驗證 3×3 或 4×4 例子，再寫代碼。
2. 原地旋轉層數 n/2，奇數階中心元素不動。
3. 四向交換順序不可亂：暫存 → 反方向覆蓋 → 最後寫入暫存值。
4. 面試中先寫輔助空間版本保證邏輯正確，有餘力再優化原地版。

矩陣旋轉是考察索引操作、邊界控制、空間優化的綜合題。掌握「轉置 + 翻轉」等價變換（順時針 90° = 轉置 + 左右翻轉），能靈活應對各種變體。