leetcode48：旋转图像

题目链接

leetcode

题目描述

给定一个 n×n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
必须在原地旋转图像，这意味着需要直接修改输入的二维矩阵，不要使用另一个矩阵。

C++ 代码

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

void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (const vector<int>& num : nums) {
        cout << "[";
        for (const int& num2 : num) {
            cout << num2 << ",";
        }
        cout << "], ";
    }
    cout << "]" <<endl;
}

/*
    分析将图像旋转 90 度之后，这些数字出现在什么位置。
    第一行的第 x 个元素，在旋转后是倒数第一列的第 x 个元素。
    对于矩阵中的第二行，在旋转后它出现在倒数第二列的位置。
    对于矩阵中的第三行和第四行，同理。
    分析规律：
        对于矩阵中第 i 行的第 j 个元素，在旋转后它出现在倒数第 i 列的第 j 个位置。
        由于矩阵中的行列从 0 开始计数，
        所以元素 matrix[i][j] 旋转后，它的新位置为 matrix[j][n-i-1]。

    辅助数组：使用一个与 matrix 大小相同的数组 matrix_new，临时存储旋转后的结果。
    在遍历完成之后，再将 matrix_new ​中的结果复制到原数组。

    时间复杂度：O(n^2)
        其中 n 是数组的长度。
    空间复杂度：O(n^2)
        使用一个和 matrix 大小相同的辅助数组。
*/
class Solution_0 {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // C++ 这里的 = 拷贝是值拷贝，会得到一个新的数组
        auto matrix_new = matrix;
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < n; j ++) {
                matrix_new[j][n - i - 1] = matrix[i][j];
            }
        }
        // 这里也是值拷贝
        matrix = matrix_new;
    }
};

/*
    操作分解：直接操作旋转 90 度比较困难，将它分解成两个操作。
    1.水平翻转：以中心的竖线为轴做翻转；
    2.对角线翻转：以左上-右下对角条线（主对角线）为轴做翻转。

    时间复杂度：O(n^2)
        其中 n 是数组的长度。
    空间复杂度：O(1)
*/
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        int n = matrix.size();
        // 水平翻转
        for (int i = 0; i < n / 2; i ++) {
            for (int j = 0; j < n; j ++) {
                swap(matrix[i][j], matrix[n - i - 1][j]);
            }
        }
        // 主对角线翻转
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < i; j ++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }

    void swap(int& a, int& b) {
        int temp = a;
        a = b;
        b = temp;
    }
};

int main() {
    Solution solution;
    vector<vector<vector<int>>> nums = {
        {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}},
        {{5, 1, 9, 11}, {2, 4, 8, 10}, {13, 3, 6, 7}, {15, 14, 12, 16}}
    };

    for (auto& num : nums) {
        cout << "Input: ";
        printArray(num);
        solution.rotate(num);
        cout << "Output: ";
        printArray(num);
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   分析规律：
       对于矩阵中第 i 行的第 j 个元素，在旋转后它出现在倒数第 i 列的第 j 个位置。
       由于矩阵中的行列从 0 开始计数，
       所以元素 matrix[i][j] 旋转后，它的新位置为 matrix[j][n-i-1]。
   基本思路：
       使用一个与 matrix 大小相同的数组 matrix_new，临时存储旋转后的结果。
       在遍历完成之后，再将 matrix_new ​中的结果复制到原数组。

   时间复杂度：O(n^2)
       其中 n 是数组的长度。
   空间复杂度：O(n^2)
       使用一个和 matrix 大小相同的辅助数组。
*/
func rotate_0(matrix [][]int) {
    n := len(matrix)
    matrix_new := make([][]int, n)
    // 创建一个新的切片来存储转置后的矩阵
    for i := 0; i < n; i ++ {
        matrix_new[i] = make([]int, n)
    }
    // 转置矩阵
    for i := 0; i < n; i ++ {
        for j := 0; j < n; j ++ {
            matrix_new[j][n - i - 1] = matrix[i][j]
        }
    }
    // 将转置后的矩阵复制回原矩阵
    for i := 0; i < n; i ++ {
        copy(matrix[i], matrix_new[i])
    }
}

/*
    水平翻转：以中心的竖线为轴做翻转；
    对角线翻转：以左上-右下对角条线为轴做翻转。
    
    时间复杂度：O(n^2)
        其中 n 是数组的长度，矩阵中的每个元素都要被访问一次。
    空间复杂度：O(1)
        直接在原始矩阵上进行操作，没有使用额外的辅助空间。
*/
func rotate(matrix [][]int) {
    n := len(matrix)
    // 水平翻转
    for i := 0; i < n / 2; i ++ {
        matrix[i], matrix[n - i - 1] = matrix[n - i - 1], matrix[i]
    }
    // 主对角线翻转
    for i := 0; i < n; i ++ {
        for j := 0; j < i; j ++ {
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }
}

func main() {
    // 测试用例
    testCases := []struct {
        matrix   [][]int
        expected [][]int
    }{
        {
            matrix: [][]int{
                {1,2,3},
                {4,5,6},
                {7,8,9},
            },
            expected: [][]int{
                {7,4,1},
                {8,5,2},
                {9,6,3},
            },
        },
        {
            matrix: [][]int{
                {5,1,9,11},
                {2,4,8,10},
                {13,3,6,7},
                {15,14,12,16},
            },
            expected: [][]int{
                {15,13,2,5},
                {14,3,4,1},
                {12,6,8,9},
                {16,7,10,11},
            },
        },
    }

    for i, tc := range testCases {
        fmt.Printf("Test Case %d, Input: matrix = %v\n", i+1, tc.matrix)
        rotate(tc.matrix)
        resultStr := fmt.Sprintf("%v", tc.matrix)
        expectedStr := fmt.Sprintf("%v", tc.expected)

        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
    }
}