作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定一个 n × n 的二维矩阵，代表一个图像，你需要将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
输入格式
- matrix：一个二维整数数组，代表一个图像。
输出格式
- 不需要返回任何结果，应当在原数组上修改，即原地旋转图像。
示例
示例 1
输入：matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] 输出：[ [7, 4, 1], [8, 5, 2], [9, 6, 3] ]
解释：该矩阵顺时针旋转 90 度后，矩阵第一行变为原矩阵的最后一列，第二行变为原矩阵的中间一列，第三行变为原矩阵的第一列，且都是从下到上的顺序。
示例 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] ]
约束条件
matrix.length == nmatrix[i].length == n1 <= n <= 20-1000 <= matrix[i][j] <= 1000
这个问题要求旋转矩阵而不使用额外的空间，即原地修改，这意味着算法需要特别注意操作的顺序和方式，以确保数据不会被错误覆盖。
方法一：转置后翻转
解题步骤
- 转置矩阵：将矩阵的行转换为列，即
matrix[i][j]与matrix[j][i]交换。 - 翻转每行：将每行的元素翻转，即首尾元素交换，实现顺时针旋转的效果。
完整的规范代码
def rotate(matrix): """ 通过转置矩阵后翻转每行来顺时针旋转图像 :param matrix: List[List[int]], n x n 的二维矩阵 :return: None """ n = len(matrix) # 转置矩阵 for i in range(n): for j in range(i + 1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # 翻转每行 for i in range(n): matrix[i].reverse() # 示例调用 matrix_example = [[1,2,3],[4,5,6],[7,8,9]] rotate(matrix_example) print(matrix_example) # 输出: [[7,4,1],[8,5,2],[9,6,3]]
算法分析
- 时间复杂度：(O(n^2))，需要遍历矩阵两次。
- 空间复杂度：(O(1))，原地修改矩阵，不需要额外空间。
方法二：层次旋转法
解题步骤
- 外层到内层：分层处理矩阵，从外层到内层逐层旋转。
- 四角替换：对于每一层，将四个角的元素依次旋转。
完整的规范代码
def rotate(matrix): """ 使用层次旋转法顺时针旋转图像 :param matrix: List[List[int]], n x n 的二维矩阵 :return: None """ n = len(matrix) for i in range(n // 2): for j in range(i, n - i - 1): temp = matrix[i][j] matrix[i][j] = matrix[n-j-1][i] matrix[n-j-1][i] = matrix[n-i-1][n-j-1] matrix[n-i-1][n-j-1] = matrix[j][n-i-1] matrix[j][n-i-1] = temp # 示例调用 matrix_example = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] rotate(matrix_example) print(matrix_example) # 输出: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
算法分析
- 时间复杂度：(O(n^2))，虽然只遍历半个矩阵，但仍然是平方级别。
- 空间复杂度：(O(1))，原地修改，无需额外空间。
方法三：递归分块法
解题步骤
- 递归分块：将矩阵视为四块小矩阵，递归地进行旋转。
- 递归基：当矩阵缩小到1x1或2x2时，直接进行手动旋转。
完整的规范代码
def rotate(matrix): """ 使用递归分块法顺时针旋转图像 :param matrix: List[List[int]], n x n 的二维矩阵 :return: None """ def rotate_submatrix(matrix, row, col, size): if size <= 1: return for i in range(size - 1): tmp = matrix[row][col + i] matrix[row][col + i] = matrix[row + size - 1 - i][col] matrix[row + size - 1 - i][col] = matrix[row + size - 1][col + size - 1 - i] matrix[row + size - 1][col + size - 1 - i] = matrix[row + i][col + size - 1] matrix[row + i][col + size - 1] = tmp rotate_submatrix(matrix, row + 1, col + 1, size - 2) rotate_submatrix(matrix, 0, 0, len(matrix)) # 示例调用 matrix_example = [[1,2,3],[4,5,6],[7,8,9]] rotate(matrix_example) print(matrix_example) # 输出: [[7,4,1],[8,5,2],[9,6,3]]
算法分析
- 时间复杂度：(O(n^2))，每个元素基本上都被处理一次，尽管是通过递归进行的。
- 空间复杂度：(O(n))，递归深度最大可能为 (n/2)，主要取决于矩阵的大小。
方法四：一次性旋转法
解题步骤
- 单次操作：直接计算每个元素旋转后的位置，将所有元素一次性放到正确位置上。
- 额外空间：使用额外的同样大小的矩阵来进行位置计算和值存储。
完整的规范代码
def rotate(matrix): """ 使用一次性旋转法顺时针旋转图像，需要额外空间 :param matrix: List[List[int]], n x n 的二维矩阵 :return: None """ n = len(matrix) new_matrix = [[0] * n for _ in range(n)] for i in range(n): for j in range(n): new_matrix[j][n-i-1] = matrix[i][j] for i in range(n): for j in range(n): matrix[i][j] = new_matrix[i][j] # 示例调用 matrix_example = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] rotate(matrix_example) print(matrix_example) # 输出: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
算法分析
- 时间复杂度：(O(n^2))，遍历一次所有元素。
- 空间复杂度：(O(n^2))，使用了额外的矩阵来存储旋转结果。
方法五：环状替换
解题步骤
- 外圈到内圈：分层处理矩阵，从外层到内层逐层旋转，每一层视为一个环。
- 环内旋转：每个元素按环进行替换，每四个元素为一组进行位置交换。
完整的规范代码
def rotate(matrix): """ 使用环状替换顺时针旋转图像 :param matrix: List[List[int]], n x n 的二维矩阵 :return: None """ n = len(matrix) layers = n // 2 for layer in range(layers): first, last = layer, n - layer - 1 for i in range(first, last): offset = i - first top = matrix[first][i] matrix[first][i] = matrix[last-offset][first] matrix[last-offset][first] = matrix[last][last-offset] matrix[last][last-offset] = matrix[i][last] matrix[i][last] = top # 示例调用 matrix_example = [[1,2,3],[4,5,6],[7,8,9]] rotate(matrix_example) print(matrix_example) # 输出: [[7,4,1],[8,5,2],[9,6,3]]
算法分析
- 时间复杂度：(O(n^2))，每个元素基本上都被处理一次。
- 空间复杂度：(O(1))，原地修改矩阵，不使用额外空间。
不同算法的优劣势对比
| 特征 | 方法一：转置后翻转 | 方法二：层次旋转法 | 方法三：递归分块法 | 方法四：一次性旋转法 | 方法五：环状替换 |
| 时间复杂度 | (O(n^2)) | (O(n^2)) | (O(n^2)) | (O(n^2)) | (O(n^2)) |
| 空间复杂度 | (O(1)) | (O(1)) | (O(n)) | (O(n^2)) | (O(1)) |
| 优势 | - 简单实用 - 快速有效 |
- 直观操作 - 无需额外空间 |
- 递归清晰 - 易于理解 |
- 计算直接 - 易于实现 |
- 高效 - 不需要额外空间 |
| 劣势 | - 需要两步处理 | - 需要精确控制边界 | - 需要额外空间 - 递归复杂 |
- 空间成本高 | - 需要精确控制层和边界 |
在选择合适的方法时，应考虑实际的需求和问题规模。例如，对于需要在有限空间内操作的场景，环状替换和层次旋转法是最优的选择；而对于能够接受一定空间换时间的场景，则可以考虑一次性旋转法或递归分块法，这些方法提供了不同的视角和实现方式，适合不同的应用环境和性能要求。
欢迎关注微信公众号 数据分析螺丝钉
