python 五种算法转置后翻转、层次旋转、递归分块、一次性旋转、环状替换 实现旋转图像【力扣题48】

简介: python 五种算法转置后翻转、层次旋转、递归分块、一次性旋转、环状替换 实现旋转图像【力扣题48】

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

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 == n
  • matrix[i].length == n
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

这个问题要求旋转矩阵而不使用额外的空间,即原地修改,这意味着算法需要特别注意操作的顺序和方式,以确保数据不会被错误覆盖。

方法一:转置后翻转

解题步骤
  1. 转置矩阵:将矩阵的行转换为列,即 matrix[i][j]matrix[j][i] 交换。
  2. 翻转每行:将每行的元素翻转,即首尾元素交换,实现顺时针旋转的效果。
完整的规范代码
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)),原地修改矩阵,不需要额外空间。

方法二:层次旋转法

解题步骤
  1. 外层到内层:分层处理矩阵,从外层到内层逐层旋转。
  2. 四角替换:对于每一层,将四个角的元素依次旋转。
完整的规范代码
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)),原地修改,无需额外空间。

方法三:递归分块法

解题步骤
  1. 递归分块:将矩阵视为四块小矩阵,递归地进行旋转。
  2. 递归基:当矩阵缩小到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),主要取决于矩阵的大小。

方法四:一次性旋转法

解题步骤
  1. 单次操作:直接计算每个元素旋转后的位置,将所有元素一次性放到正确位置上。
  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)),使用了额外的矩阵来存储旋转结果。

方法五:环状替换

解题步骤
  1. 外圈到内圈:分层处理矩阵,从外层到内层逐层旋转,每一层视为一个环。
  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))
优势 - 简单实用
- 快速有效
- 直观操作
- 无需额外空间
- 递归清晰
- 易于理解
- 计算直接
- 易于实现
- 高效
- 不需要额外空间
劣势 - 需要两步处理 - 需要精确控制边界 - 需要额外空间
- 递归复杂
- 空间成本高 - 需要精确控制层和边界

在选择合适的方法时,应考虑实际的需求和问题规模。例如,对于需要在有限空间内操作的场景,环状替换和层次旋转法是最优的选择;而对于能够接受一定空间换时间的场景,则可以考虑一次性旋转法或递归分块法,这些方法提供了不同的视角和实现方式,适合不同的应用环境和性能要求。


欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
5天前
|
缓存 Python
Python中递归错误
【7月更文挑战第17天】
16 8
|
1天前
|
算法 计算机视觉 Python
|
6天前
|
机器学习/深度学习 编解码 算法框架/工具
使用Python实现深度学习模型:图像超分辨率与去噪
【7月更文挑战第17天】 使用Python实现深度学习模型:图像超分辨率与去噪
22 4
|
4天前
|
算法 Python
python中算法递归错误(Recursion Errors)
【7月更文挑战第18天】
10 1
|
6天前
|
机器学习/深度学习 人工智能 自然语言处理
|
6天前
|
算法
基于粒子群优化的图像融合算法matlab仿真
这是一个基于粒子群优化(PSO)的图像融合算法,旨在将彩色模糊图像与清晰灰度图像融合成彩色清晰图像。在MATLAB2022a中测试,算法通过PSO求解最优融合权值参数,经过多次迭代更新粒子速度和位置,以优化融合效果。核心代码展示了PSO的迭代过程及融合策略。最终,使用加权平均法融合图像,其中权重由PSO计算得出。该算法体现了PSO在图像融合领域的高效性和融合质量。
|
7天前
|
存储 缓存 算法
python中递归深度超限(RecursionError)
【7月更文挑战第15天】
12 1
|
8天前
|
机器学习/深度学习 数据可视化 TensorFlow
使用Python实现深度学习模型:图像语义分割与对象检测
【7月更文挑战第15天】 使用Python实现深度学习模型:图像语义分割与对象检测
28 2
|
10天前
|
机器学习/深度学习 TensorFlow 算法框架/工具
使用Python实现深度学习模型:图像风格迁移与生成
【7月更文挑战第13天】 使用Python实现深度学习模型:图像风格迁移与生成
15 2
|
9天前
|
资源调度 计算机视觉 Python
`scipy.ndimage`是SciPy库中的一个子模块,它提供了许多用于处理n维数组(通常是图像)的函数。
`scipy.ndimage`是SciPy库中的一个子模块,它提供了许多用于处理n维数组(通常是图像)的函数。