DSA问题：寻找矩阵数组中各矩阵镜像的更优解法

核心思路：哈希映射预处理 #

暴力遍历的问题在于每次判断都要逐个比较矩阵元素，时间复杂度是O(n²*m)（n是矩阵数量，m是单个矩阵的元素总数）。优化的关键是提前把每个矩阵及其镜像的特征值存入哈希表，后续查找直接O(1)查询。

具体步骤 #

• 预处理阶段：遍历所有矩阵，对每个矩阵生成两个关键值：
  1. 原矩阵的序列化特征：把二维矩阵转成不可变的一维结构（比如将[[1,0],[0,1]]转成((1,0),(0,1))），作为哈希表的键，值存矩阵的索引。
  2. 该矩阵的镜像矩阵的序列化特征：先生成矩阵的镜像（这里默认是水平镜像，即每行反转；如果是垂直镜像则反转行的顺序，需根据需求确认），同样转成序列化特征。
• 查询阶段：对每个矩阵，直接用它的镜像序列化特征去哈希表里查对应的索引，存在则返回该索引，不存在返回-1。

示例代码（Python） #

def get_mirror(matrix):
    # 水平镜像：每行反转，若需求为垂直镜像可改为 return matrix[::-1]
    return [row[::-1] for row in matrix]

def matrix_to_key(matrix):
    # 转成不可变元组作为哈希键
    return tuple(tuple(row) for row in matrix)

# 示例输入
matrices = [
    [[1,0,0],[1,0,1],[1,1,1]],
    [[1,1,1],[0,0,0],[0,1,1]],
    [[0,0,0],[1,1,1],[1,0,0]],
    [[0,1,1],[0,1,0],[0,0,0]]
]

# 构建哈希映射
matrix_map = {}
for idx, mat in enumerate(matrices):
    key = matrix_to_key(mat)
    matrix_map[key] = idx

# 生成结果
result = []
for mat in matrices:
    mirror_mat = get_mirror(mat)
    mirror_key = matrix_to_key(mirror_mat)
    result.append(str(matrix_map.get(mirror_key, -1)))

print(' '.join(result))  # 输出：3 2 1 0

复杂度分析 #

• 预处理时间：O(n*m)，n是矩阵数量，m是单个矩阵元素数，每个矩阵序列化和生成镜像都是线性时间。
• 查询时间：O(n*m)，每个矩阵生成镜像并查询哈希表，哈希表查询是O(1)。
• 整体时间复杂度比暴力法的O(n²*m)大幅降低，尤其是当矩阵数量n很大时，优化效果明显。

内容的提问来源于stack exchange，提问作者Abhishree Tripathi