旋转图像工具 - KMP鸿蒙算法实现
欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net
摘要
旋转图像工具实现了将 n x n 的二维矩阵顺时针旋转 90 度的功能。本文详细解析了输入解析、转置+翻转法、四元素交换法等核心功能的代码实现细节。
1. 算法背景
1.1 问题描述
给定一个 n x n 的二维矩阵，将其顺时针旋转 90 度。要求原地修改矩阵，不使用额外的矩阵空间。
示例：
-
输入：
1 2 3 4 5 6 7 8 9 -
输出：
7 4 1 8 5 2 9 6 3
1.2 应用场景
- 图像处理
- 矩阵变换
- 游戏开发
- 算法竞赛
2. 核心算法原理
2.1 转置+翻转法（推荐）
先转置矩阵（行列互换），然后翻转每一行。时间复杂度 O(n²)，空间复杂度 O(1)。
2.2 四元素交换法
一次交换四个位置的元素，通过层的方式从外到内旋转。时间复杂度 O(n²)，空间复杂度 O(1)。
3. 代码实现详细解析
3.1 输入解析模块
var matrix: List<List<Int>>? = null
payload.lines()
.map { it.trim() }
.filter { it.isNotEmpty() }
.forEach { line ->
if (line.startsWith("matrix=", ignoreCase = true)) {
val valuesStr = line.substringAfter("=").trim()
// 尝试解析为矩阵
val lines = if (valuesStr.contains("\n")) {
valuesStr.split("\n").map { it.trim() }
} else {
listOf(valuesStr)
}
try {
if (lines.size == 1) {
// 单行格式，尝试推断矩阵大小
val nums = lines[0].split(",")
.map { it.trim() }
.filter { it.isNotEmpty() }
.map { it.toInt() }
// 计算矩阵大小：找到n使得n*n==nums.size
var n = 1
while (n * n < nums.size) {
n++
}
if (n * n == nums.size) {
matrix = (0 until n).map { row ->
(0 until n).map { col ->
nums[row * n + col]
}
}
}
}
} catch (e: Exception) {
matrix = null
}
}
}
代码解析：
这段代码实现了灵活的矩阵输入解析机制，支持单行和多行格式。首先声明一个可空的二维整数列表 matrix，初始值为 null。
然后使用函数式编程风格处理输入：payload.lines() 将输入按行分割，map { it.trim() } 去除每行的首尾空白字符，filter { it.isNotEmpty() } 过滤空行。
在 forEach 循环中，检查是否以 matrix= 开头。提取等号后面的部分作为矩阵字符串，然后检查是否包含换行符（\n）。如果包含换行符，按换行符分割成多行；否则，将其作为单行处理。
对于单行格式（如 1,2,3,4,5,6,7,8,9），首先按逗号分割并转换为整数列表。然后计算矩阵大小：通过循环找到 n，使得 n * n == nums.size。例如，对于 9 个数字，n = 3，因为 3 * 3 = 9。
如果找到了合适的 n，则将一维数组转换为二维矩阵：(0 until n).map { row -> (0 until n).map { col -> nums[row * n + col] } }。这个表达式为每一行创建一个列表，每一行的元素从一维数组中按行优先顺序提取。
对于多行格式，直接将每一行按逗号分割并转换为整数列表，形成一个二维列表。
使用 try-catch 块捕获可能的异常，确保程序的健壮性。如果解析失败，将 matrix 设置为 null。
3.2 转置+翻转法实现（推荐）
fun rotateTransposeFlip(matrix: List<List<Int>>): List<List<Int>> {
val n = matrix.size
val result = matrix.map { it.toMutableList() }.toMutableList()
// 转置
for (i in 0 until n) {
for (j in i + 1 until n) {
val temp = result[i][j]
result[i][j] = result[j][i]
result[j][i] = temp
}
}
// 翻转每一行
for (i in 0 until n) {
result[i].reverse()
}
return result.map { it.toList() }
}
代码解析：
这是转置+翻转法的核心实现，通过两个步骤实现矩阵的顺时针旋转。函数接受一个二维整数列表作为参数，返回旋转后的矩阵。
首先获取矩阵大小 n，然后创建结果矩阵。使用 matrix.map { it.toMutableList() }.toMutableList() 创建一个可变的副本，这样可以在原地修改。
第一步是转置矩阵：转置是指将矩阵的行和列互换，即 matrix[i][j] 变成 matrix[j][i]。
使用嵌套循环遍历矩阵的上三角部分（i 从 0 到 n-1，j 从 i+1 到 n-1）。对于每个位置 (i, j)，交换 result[i][j] 和 result[j][i]。只遍历上三角部分是为了避免重复交换，因为如果遍历整个矩阵，每个元素会被交换两次，结果回到原状。
例如，对于矩阵：
1 2 3
4 5 6
7 8 9
转置后变成：
1 4 7
2 5 8
3 6 9
第二步是翻转每一行：使用 result[i].reverse() 翻转每一行，将每一行的元素顺序反转。
例如，对于转置后的矩阵：
1 4 7
2 5 8
3 6 9
翻转每一行后变成：
7 4 1
8 5 2
9 6 3
这就是顺时针旋转 90 度后的结果。
最后，将可变的矩阵转换为不可变的列表并返回：result.map { it.toList() }。
这个算法的时间复杂度是 O(n²)，其中 n 是矩阵的大小，因为需要遍历矩阵的所有元素。空间复杂度是 O(1)（不考虑输出空间），因为只使用了固定数量的变量，原地修改矩阵。
3.3 四元素交换法实现
fun rotateFourElements(matrix: List<List<Int>>): List<List<Int>> {
val n = matrix.size
val result = matrix.map { it.toMutableList() }.toMutableList()
for (i in 0 until n / 2) {
for (j in i until n - 1 - i) {
val temp = result[i][j]
result[i][j] = result[n - 1 - j][i]
result[n - 1 - j][i] = result[n - 1 - i][n - 1 - j]
result[n - 1 - i][n - 1 - j] = result[j][n - 1 - i]
result[j][n - 1 - i] = temp
}
}
return result.map { it.toList() }
}
代码解析：
这是四元素交换法的实现，通过一次交换四个位置的元素来实现旋转。函数接受一个二维整数列表作为参数，返回旋转后的矩阵。
首先获取矩阵大小 n，然后创建结果矩阵的可变副本。
使用嵌套循环，外层循环 i 从 0 到 n / 2 - 1，表示从外到内的层数。内层循环 j 从 i 到 n - 1 - i，表示当前层中的位置。
对于每个位置 (i, j)，需要交换四个位置的元素：
(i, j)→ 顺时针旋转90度 →(j, n - 1 - i)(j, n - 1 - i)→ 顺时针旋转90度 →(n - 1 - i, n - 1 - j)(n - 1 - i, n - 1 - j)→ 顺时针旋转90度 →(n - 1 - j, i)(n - 1 - j, i)→ 顺时针旋转90度 →(i, j)
这四个位置形成一个循环，可以通过一次交换完成。首先保存 result[i][j] 到临时变量 temp，然后依次交换：
result[i][j] = result[n - 1 - j][i]result[n - 1 - j][i] = result[n - 1 - i][n - 1 - j]result[n - 1 - i][n - 1 - j] = result[j][n - 1 - i]result[j][n - 1 - i] = temp
这样一次交换就完成了四个元素的旋转。
例如，对于矩阵的四个角：
a b
c d
交换后变成：
c a
d b
这个算法的时间复杂度是 O(n²)，空间复杂度是 O(1)（不考虑输出空间），因为只使用了固定数量的变量。虽然效率与转置+翻转法相同，但实现更复杂，需要仔细处理索引计算。
3.4 矩阵大小推断
// 计算矩阵大小：找到n使得n*n==nums.size
var n = 1
while (n * n < nums.size) {
n++
}
if (n * n == nums.size) {
matrix = (0 until n).map { row ->
(0 until n).map { col ->
nums[row * n + col]
}
}
}
代码解析：
这段代码实现了从一维数组推断矩阵大小的功能。对于单行格式的输入（如 1,2,3,4,5,6,7,8,9），需要自动推断矩阵的大小。
首先初始化 n = 1，然后使用 while 循环，不断增加 n，直到 n * n >= nums.size。这个循环找到最小的 n，使得 n * n 大于等于数组的大小。
然后检查 n * n == nums.size，如果相等，说明数组的大小是完美平方数，可以组成 n x n 的矩阵。否则，说明无法组成正方形矩阵。
如果能够组成矩阵，则使用 (0 until n).map { row -> (0 until n).map { col -> nums[row * n + col] } } 将一维数组转换为二维矩阵。这个表达式为每一行创建一个列表，每一行的元素从一维数组中按行优先顺序提取。索引计算是 row * n + col，其中 row 是行索引，col 是列索引。
4. 算法复杂度分析
4.1 时间复杂度
- 转置+翻转法：O(n²)，需要遍历矩阵的所有元素
- 四元素交换法：O(n²)，需要遍历矩阵的所有元素
- 总体时间复杂度：O(n²)
4.2 空间复杂度
- 转置+翻转法：O(1)（不考虑输出空间），只使用固定数量的变量
- 四元素交换法：O(1)（不考虑输出空间），只使用固定数量的变量
- 总体空间复杂度：O(1)
5. 算法优化建议
5.1 原地修改优化
两种方法都支持原地修改，空间复杂度为 O(1)。
5.2 边界条件处理
代码已经处理了各种边界情况：1x1 矩阵、2x2 矩阵等情况。
5.3 性能优化
两种方法的时间复杂度相同，转置+翻转法实现更简单，推荐使用。
6. 应用场景扩展
- 图像处理：旋转图像、调整图像方向
- 矩阵变换：图形变换、坐标转换
- 游戏开发：游戏中的图像旋转、精灵旋转
- 算法竞赛：LeetCode 等平台的经典问题
- 扩展问题：逆时针旋转、180度旋转、任意角度旋转等变体
7. 总结
旋转图像工具实现了两种旋转方法，核心要点：
- 转置+翻转法：推荐，实现简单，先转置后翻转每一行
- 四元素交换法：一次交换四个位置的元素，实现更复杂
- 原地修改：两种方法都支持原地修改，空间复杂度 O(1)
- 时间复杂度：两种方法都是 O(n²)
通过深入理解代码实现，可以更好地应用这个算法解决实际问题，如图像处理、矩阵变换、游戏开发等场景。转置+翻转法的思想也可以应用到其他类似的矩阵变换问题中。
开源鸿蒙跨平台开发社区汇聚开发者与厂商，共建“一次开发，多端部署”的开源生态，致力于降低跨端开发门槛，推动万物智联创新。
更多推荐
17
0- 0
已为社区贡献6条内容
所有评论(0)