LeetCode 1632. 矩阵转换后的秩 题目描述 给定一个 m x n 的矩阵 matrix ，返回一个新矩阵 answer ，其中 answer[i][j] 是 matrix[i][j] 的秩。秩的定义如下： 秩是一个从 1 开始的正整数。 如果两个元素 p 和 q 在同一行或者同一列，那么： 如果 p < q ，那么 p 的秩必须严格小于 q 的秩。 如果 p == q ，那么它们的秩必须相同。 如果 p > q ，那么 p 的秩必须严格大于 q 的秩。 秩应当尽可能小。 示例 输入：matrix = [ [ 1,2],[ 3,4] ] 输出：[ [ 1,2],[ 2,3] ] 解释： matrix[ 0][ 0 ] = 1，秩为 1 matrix[ 0][ 1 ] = 2，大于 1，且在同一行，秩为 2 matrix[ 1][ 0 ] = 3，大于 1，且在同一列，秩为 2 matrix[ 1][ 1 ] = 4，大于 2 和 3，且在同一行/列，秩为 3 解题步骤 第一步：理解问题与难点 约束条件复杂 ：每个元素受同行、同列所有元素的相对大小约束。 相等元素的特殊处理 ：相等元素的秩必须相同，这会将多个位置“绑定”在一起。 贪心思路 ：如果我们从小到大处理元素，可以逐步分配秩。但相等元素需同时处理，且后续元素可能受前面多个位置的影响。 第二步：核心思路 排序所有元素 ：将矩阵所有位置按值从小到大排序，值相同的放入同一组。 并查集管理相等元素 ：同一组相等元素，无论行列关系，它们的秩最终必须相同，因此将这些位置用并查集合并为一个连通分量。 拓扑排序确定秩 ： 每个并查集根节点代表一个组件。 对每个组件，找出其受哪些其他组件约束（即同行/列中比它小的最大值对应的组件）。 建立组件间的有向边（小秩 → 大秩），进行拓扑排序，逐步分配最小可能的秩。 第三步：详细步骤拆解 步骤 1：数据准备 记录每个元素的行、列、值，存入列表。 按值排序，相同值的分组处理。 步骤 2：并查集合并相等元素 对每个值相同的组： 因为这些元素秩必须相同，但可能散布在不同行/列，我们合并同一行或同一列中的相等元素。 具体方法：用两个哈希表 rowRoot 和 colRoot ，分别记录当前行/列最近处理的相等元素位置。如果当前行之前出现过相等元素，就合并两个位置到同一并查集；列同理。 步骤 3：建立组件间的依赖图 初始化两个数组 maxRankInRow 和 maxRankInCol ，记录每行/列当前已分配的最大秩对应的组件根节点。 遍历排序后的元素（按值从小到大，同值的一起处理）： 对每个元素找到其并查集根节点 root 。 查询 maxRankInRow[row] 和 maxRankInCol[col] ，得到该行/列之前已分配的最大秩的组件 prevRoot 。 如果 prevRoot 存在且与 root 不同，说明 root 的秩必须大于 prevRoot 的秩，因此在图中添加边 prevRoot → root 。 更新 maxRankInRow[row] 和 maxRankInCol[col] 为 root 。 步骤 4：拓扑排序分配秩 对建立的图进行拓扑排序： 计算每个组件的入度。 入度为 0 的组件初始秩为 1。 按拓扑顺序，每个组件的秩 = max(所有前驱组件的秩) + 1。 每个元素的秩 = 其所在组件的秩。 步骤 5：填充结果矩阵 根据每个位置对应的并查集根节点组件，得到该组件的秩，填入 answer[i][j] 。 举例说明 矩阵： [ [ 1, 2 ], [ 3, 4] ] 排序所有位置（值, i, j）： (1,0,0), (2,0,1), (3,1,0), (4,1,1) 没有相等值，每个元素自成一个组件。 处理 (1,0,0)： 行 0 之前最大组件：无；列 0 之前最大组件：无 分配秩 1，更新行 0、列 0 的最大组件为 (0,0) 处理 (2,0,1)： 行 0 最大组件为 (0,0)，秩 1；列 1 无 因此 (0,1) 秩必须 > (0,0) 的秩，最小为 2 更新行 0、列 1 最大组件为 (0,1) 处理 (3,1,0)： 行 1 无；列 0 最大组件为 (0,0)，秩 1 秩最小为 2 更新行 1、列 0 最大组件为 (1,0) 处理 (4,1,1)： 行 1 最大组件为 (1,0)，秩 2；列 1 最大组件为 (0,1)，秩 2 秩必须大于 2，最小为 3 更新行 1、列 1 最大组件为 (1,1) 结果：[ [ 1,2],[ 2,3] ] 复杂度分析 时间复杂度：O(mn log(mn))，排序占主导，并查集操作近似常数。 空间复杂度：O(mn)，存储位置、并查集、图结构。 此算法将复杂的行列约束转化为图论问题，用并查集处理相等元素，拓扑排序处理不等关系，确保每一步分配的秩尽可能小。