LeetCode 算法： 旋转图像c++

LeetCode 算法： 旋转图像c++

引用

CSDN

1.

https://blog.csdn.net/yanceyxin/article/details/139637278

在算法面试和编程练习中，LeetCode是一个不可或缺的平台。本文将详细讲解LeetCode上一道经典的图像处理题目：旋转图像。通过学习本文，你将掌握如何使用辅助数组法实现图像的顺时针旋转90度，并通过具体的C++代码示例加深理解。

题目描述

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

要求：

• 必须在原地旋转图像，即直接修改输入的二维矩阵。
• 不要使用另一个矩阵来旋转图像。

示例 1

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

解题思路

要将一个 n × n 的二维矩阵（代表一个图像）顺时针旋转 90 度，你可以遵循以下解题思路：

1. 理解问题：首先，理解顺时针旋转90度意味着什么。对于矩阵中的每个元素，它将移动到原始位置的左上角方向。
2. 创建新矩阵：由于旋转后的矩阵大小不会改变，你可以使用与原始矩阵相同大小的新矩阵来存储结果。
3. 遍历原始矩阵：遍历原始矩阵的每个元素，确定它们在新矩阵中的位置。对于矩阵中的每个元素 matrix[i][j]，它将在新矩阵中的位置是 new_matrix[j][n-1-i]。
4. 填充新矩阵：按照上述规则，将原始矩阵的元素复制到新矩阵的相应位置。
5. 优化空间：如果不需要保留原始矩阵，你可以在原地修改矩阵以节省空间。这可以通过先交换行，然后反转每一行来实现。
6. 代码实现：根据上述逻辑，编写代码实现矩阵的旋转。
7. 测试：编写测试用例来验证你的解决方案是否正确。确保测试包括各种大小的矩阵，包括特殊情况，如 n=1 或 n=2。
8. 考虑边界条件：确保你的解决方案能够处理矩阵的边界条件，例如矩阵的第一行和第一列。
9. 性能分析：分析你的解决方案的时间和空间复杂度。理想情况下，时间复杂度应该是 O(n^2)，因为每个元素都被访问一次，空间复杂度应该是 O(1)，如果原地旋转的话。
10. 代码优化：如果可能，尝试优化你的代码，使其更简洁或提高性能。

这种方法不需要额外的空间，因为它直接在原始矩阵上进行操作。但请注意，这种方法会修改原始矩阵，如果需要保留原始矩阵，则需要先复制一份。

复杂度分析

• 时间复杂度：O(n^2)，因为需要遍历整个矩阵。
• 空间复杂度：O(n^2)，因为使用了额外的矩阵存储旋转后的结果。

C++代码实现

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

void rotateMatrix(vector<vector<int>>& matrix) {
    int n = matrix.size();
    vector<vector<int>> newMatrix(n, vector<int>(n));
    // 将原始矩阵的元素复制到新矩阵中
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            newMatrix[j][n - 1 - i] = matrix[i][j];
        }
    }
    // 将新矩阵赋值回原始矩阵
    matrix = newMatrix;
}

void printMatrix(const vector<vector<int>>& matrix) {
    for (const auto& row : matrix) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
}

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    cout << "Original Matrix:" << endl;
    printMatrix(matrix);
    rotateMatrix(matrix);
    cout << "Rotated Matrix:" << endl;
    printMatrix(matrix);
    cout << endl;

    vector<vector<int>> matrix2 = {
        {5,  1,  9,  11},
        {2,  4,  8,  10},
        {13, 3,  6,  7 },
        {15, 14, 12, 16}
    };
    cout << "Original Matrix2:" << endl;
    printMatrix(matrix2);
    rotateMatrix(matrix2);
    cout << "Rotated Matrix2:" << endl;
    printMatrix(matrix2);

    return 0;
}

• 输出结果：

Original Matrix:
1 2 3
4 5 6
7 8 9
Rotated Matrix:
7 4 1
8 5 2
9 6 3

Original Matrix2:
5 1 9 11
2 4 8 10
13 3 6 7
15 14 12 16
Rotated Matrix2:
15 13 2 5
14 3 4 1
12 6 8 9
16 7 10 11