题解

问题本质

判断两个矩阵能否通过交换行和交换列互相转换。

关键观察

1. 行交换和列交换是独立的：行操作不影响列内元素的相对顺序，列操作不影响行内元素的相对顺序。

2. 特征不变性：无论怎样交换行，每行的元素集合保持不变；无论怎样交换列，每列的元素集合保持不变。

3. 相似条件：两个矩阵相似当且仅当：

   • 它们有相同的行多集合（每行的元素集合）
   • 它们有相同的列多集合（每列的元素集合）

解法思路

1. 验证元素集合：首先检查两个矩阵包含的元素是否完全相同。

2. 行特征匹配：

   • 对每个矩阵，将每行的元素排序，得到该行的"特征"
   • 比较两个矩阵的行特征多集合是否相同

3. 列特征匹配：

   • 对每个矩阵，将每列的元素排序，得到该列的特征
   • 比较两个矩阵的列特征多集合是否相同

4. 结论：如果行特征和列特征都匹配，则矩阵相似；否则不相似。

复杂度

• 时间复杂度：$O(nm\log m + mn\log n)$
• 空间复杂度：$O(nm)$

其中 $n$ 为行数，$m$ 为列数。