豆包MarsCode算法题：小U的矩阵转置计算

问题描述

思路分析

1. 理解题目

我们需要计算矩阵的转置权值，定义如下：

• 将矩阵转置后，计算每个对应位置元素的绝对差。
• 累加所有绝对差，得到最终的转置权值。

转置的含义：

• 原矩阵 a[i][j] 在转置矩阵中位于位置 b[j][i] 。

转置权值公式：

• 对于每对位置 (i, j) ，计算差值： | a[i][j] - a[j][i] |
• 累加所有位置的差值，得到结果。

2. 优化操作

通过矩阵对称性观察：

1. 如果 i = j （对角线元素），那么 a[i][j] = a[j][i] ，差值为 0。
2. 如果 i ≠ j ，则差值需要实际计算。

减少重复计算：
由于 | a[i][j] - a[j][i] | 的对称性，只需计算上三角或下三角区域的差值即可（即排除对角线），这样我们就可以减少一半的重复运算。

3. 实现步骤

1. 初始化结果变量：用于累加差值。
2. 遍历矩阵的上三角区域（排除对角线）：
   • 对于每对 (i, j) 和 (j, i) ，计算 | a[i][j] - a[j][i] | 。
3. 累加差值。

4. 时间复杂度

矩阵大小为 n × n ，遍历上三角区域需要计算约 n²/2 次。因此，时间复杂度为：O(n²)

参考代码（Python）

def solution(n: int, a: list) -> int:
    # 初始化转置权值
    transpose_weight = 0
    
    # 遍历矩阵的每个元素
    for i in range(n):
        for j in range(n):
            # 计算 |a[i][j] - a[j][i]| 并累加
            transpose_weight += abs(a[i][j] - a[j][i])
    
    return transpose_weight

if __name__ == '__main__':
    # 测试用例
    print(solution(2, [[1, 2], [3, 4]]) == 2)  
    print(solution(3, [[1, 2, 3], [4, 5, 6], [7, 8, 9]]) == 16)  
    print(solution(4, [[1, 1, 1, 1], [2, 2, 2, 2], [3, 3, 3, 3], [4, 4, 4, 4]]) == 20) 

代码分析

1. 函数定义和输入参数

def solution(n: int, a: list) -> int:

• n：矩阵的大小（行和列数）。
• a：一个 n × n 的二维列表，表示输入矩阵。

2. 初始化结果变量

transpose_weight = 0

• transpose_weight 是用来存储累加的转置权值。
• 初始值为 0，随着每次遍历矩阵元素计算差值后累加。

3. **双重循环遍历矩阵

for i in range(n):
    for j in range(n):
        # 计算 |a[i][j] - a[j][i]| 并累加
        transpose_weight += abs(a[i][j] - a[j][i])

逻辑解释：

• 外层循环 for i in range(n) 遍历矩阵的行。
• 内层循环 for j in range(n) 遍历矩阵的列。

对于每个矩阵元素 a[i][j]：

• 访问原矩阵：a[i][j]
• 访问转置矩阵：a[j][i]（转置操作就是行列互换）
• 计算对应元素的绝对差值：abs(a[i][j] - a[j][i])
• 将差值累加到 transpose_weight。

4. 返回结果

return transpose_weight

• 遍历完成后，transpose_weight 累积了所有位置的绝对差值，作为最终的转置权值。

原文地址：https://blog.csdn.net/2302_79730293/article/details/143818994

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！