旋转图像

题目要求

给定一个 n × n 的二维矩阵 matrix，代表一个图像。要求将图像顺时针旋转 90 度。必须在原地旋转图像，即直接修改输入的二维矩阵，不允许使用另一个矩阵来旋转图像。

解题思路

顺时针旋转图像 90 度，可以分解为两个步骤：

转置矩阵：将矩阵的行转换成列，即 matrix[i][j] 与 matrix[j][i] 交换。
反转每一行：将每一行的元素反向排列，即第一个元素与最后一个元素交换，这样做是为了实现顺时针旋转的效果。

具体步骤如下：

首先，遍历矩阵的上半部分（对角线以上的部分），对于矩阵中的元素 matrix[i][j]，与其对称位置的元素 matrix[j][i] 进行交换。
然后，对矩阵的每一行进行反转操作，即将第 i 行的第 j 个元素与第 n-j-1 个元素交换，其中 n 是矩阵的大小。

这样，就可以实现在原地对矩阵进行顺时针旋转 90 度的操作。注意，这种方法只适用于 n × n 的矩阵，即宽度和高度相等的情况。

Golang 版本

package main

import "fmt"

func rotate(matrix [][]int) {
    n := len(matrix)
    // Transpose the matrix
    for i := 0; i < n; i++ {
        for j := i; j < n; j++ {
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }
    // Reverse each row
    for i := 0; i < n; i++ {
        for j := 0; j < n/2; j++ {
            matrix[i][j], matrix[i][n-j-1] = matrix[i][n-j-1], matrix[i][j]
        }
    }
}

func main() {
    // Example matrix
    matrix := [][]int{
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9},
    }
    rotate(matrix)
    fmt.Println(matrix)
}

这段 Go 语言代码实现了上述的解题思路，首先对矩阵进行转置，然后反转每一行，以达到顺时针旋转 90 度的效果。在 main 函数中，定义了一个示例矩阵，并调用 rotate 函数来旋转这个矩阵，最后打印出旋转后的矩阵。

C++版本

#include <iostream>
#include <vector>

void rotate(std::vector<std::vector<int>>& matrix) {
    int n = matrix.size();
    // Transpose the matrix
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            std::swap(matrix[i][j], matrix[j][i]);
        }
    }
    // Reverse each row
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n / 2; ++j) {
            std::swap(matrix[i][j], matrix[i][n - j - 1]);
        }
    }
}

int main() {
    std::vector<std::vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    rotate(matrix);

    // Output the rotated matrix
    for (const auto &row : matrix) {
        for (int val : row) {
            std::cout << val << ' ';
        }
        std::cout << '\n';
    }

    return 0;
}

这段 C++ 代码实现了矩阵的原地顺时针旋转 90 度。首先，通过双重循环对矩阵进行转置，然后再通过双重循环将每一行反转。在 main 函数中，定义了一个示例矩阵，并调用 rotate 函数来旋转这个矩阵，最后通过嵌套循环打印出旋转后的矩阵。

Python 版本

def rotate(matrix):
    n = len(matrix)
    # Transpose the matrix
    for i in range(n):
        for j in range(i, n):
            matrix[j][i], matrix[i][j] = matrix[i][j], matrix[j][i]

    # Reverse each row
    for i in range(n):
        matrix[i].reverse()

# Example usage
if __name__ == "__main__":
    matrix = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]
    ]
    rotate(matrix)
    for row in matrix:
        print(row)

这段 Python 代码实现了矩阵的原地顺时针旋转 90 度。首先，通过双重循环对矩阵进行转置，然后使用列表的 reverse() 方法将每一行反转。在 if __name__ == "__main__": 块中，定义了一个示例矩阵，并调用 rotate 函数来旋转这个矩阵，最后通过循环打印出旋转后的矩阵。

Java 版本

public class MatrixRotation {
    public static void rotate(int[][] matrix) {
        int n = matrix.length;
        // Transpose the matrix
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        // Reverse each row
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };

        rotate(matrix);

        // Print the rotated matrix
        for (int[] row : matrix) {
            for (int val : row) {
                System.out.print(val + " ");
            }
            System.out.println();
        }
    }
}

这段 Java 代码实现了矩阵的原地顺时针旋转 90 度。首先，通过双重循环对矩阵进行转置，然后再通过双重循环将每一行反转。在 main 方法中，定义了一个示例矩阵，并调用 rotate 方法来旋转这个矩阵，最后通过嵌套循环打印出旋转后的矩阵。

Rust 版本

fn rotate(matrix: &mut Vec<Vec<i32>>) {
    let n = matrix.len();
    // Transpose the matrix
    for i in 0..n {
        for j in (i + 1)..n {
            let temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    // Reverse each row
    for row in matrix {
        row.reverse();
    }
}

fn main() {
    let mut matrix = vec![
        vec![1, 2, 3],
        vec![4, 5, 6],
        vec![7, 8, 9],
    ];
    rotate(&mut matrix);
    for row in matrix {
        println!("{:?}", row);
    }
}

这段 Rust 代码实现了矩阵的原地顺时针旋转 90 度。首先，通过两层循环对矩阵进行转置，然后使用 reverse() 方法将每一行反转。在 main 函数中，定义了一个示例矩阵，并调用 rotate 函数来旋转这个矩阵，最后通过循环打印出旋转后的矩阵。

总结

无论是在哪种编程语言中，顺时针旋转一个 n × n 的二维矩阵 90 度的问题，都可以通过两个步骤来解决：

转置矩阵：这一步涉及将矩阵的行转换成列。具体操作是遍历矩阵的上半部分（对角线以上的部分），交换位置在 (i, j) 和 (j, i) 的元素，其中 i 是行索引，j 是列索引。
反转每一行：转置后，每一行的元素都是旋转后列的逆序，因此需要将每一行的元素反转，以获得正确的顺序。

在实现代码时，首先通过嵌套循环对矩阵进行转置，然后在每一行上调用反转操作。在不同的编程语言中，这些操作可能有不同的语法和函数调用，但基本算法逻辑是一致的。

在 C++ 中，使用 std::swap 来交换元素，以及通过索引访问和修改矩阵。
在 Python 中，可以直接交换元素，并使用列表的 reverse() 方法或切片来反转每一行。
在 Java 中，使用临时变量来交换元素，并通过索引访问和修改矩阵。
在 Rust 中，使用模式匹配来交换元素，并使用 reverse() 方法来反转每一行。

这种解法的空间复杂度为 O(1)，因为它是在原地进行操作，不需要额外的存储空间。时间复杂度为 O(n^2)，因为需要遍历矩阵中的每个元素。

hot-100