矩阵转换后的秩

难度: Hard

给你一个 m x n 的矩阵 matrix ，请你返回一个新的矩阵 answer ，其中 answer[row][col] 是 matrix[row][col] 的秩。

每个元素的秩是一个整数，表示这个元素相对于其他元素的大小关系，它按照如下规则计算：

秩是从 1 开始的一个整数。
如果两个元素 p 和 q 在 同一行 或者 同一列 ，那么：
- 如果 p < q ，那么 rank(p) < rank(q)
- 如果 p == q ，那么 rank(p) == rank(q)
- 如果 p > q ，那么 rank(p) > rank(q)
秩需要越小越好。

题目保证按照上面规则 answer 数组是唯一的。

示例 1：

输入：matrix = [[1,2],[3,4]]
输出：[[1,2],[2,3]]
解释：
matrix[0][0] 的秩为 1 ，因为它是所在行和列的最小整数。
matrix[0][1] 的秩为 2 ，因为 matrix[0][1] > matrix[0][0] 且 matrix[0][0] 的秩为 1 。
matrix[1][0] 的秩为 2 ，因为 matrix[1][0] > matrix[0][0] 且 matrix[0][0] 的秩为 1 。
matrix[1][1] 的秩为 3 ，因为 matrix[1][1] > matrix[0][1]， matrix[1][1] > matrix[1][0] 且 matrix[0][1] 和 matrix[1][0] 的秩都为 2 。

示例 2：

输入：matrix = [[7,7],[7,7]]
输出：[[1,1],[1,1]]

示例 3：

输入：matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]
输出：[[4,2,3],[1,3,4],[5,1,6],[1,3,4]]

示例 4：

输入：matrix = [[7,3,6],[1,4,5],[9,8,2]]
输出：[[5,1,4],[1,2,3],[6,3,1]]

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 500
-10⁹ <= matrix[row][col] <= 10⁹

Submission

运行时间: 383 ms

内存: 63.6 MB

class Solution:
    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:
        m, n = len(matrix), len(matrix[0])
        sep = m + 1 if m > n else n + 1
        parents = list(range(2 * sep))

        def find(x):
            while x != parents[x]:
                parents[x] = x = parents[parents[x]]
            return x

        groups = defaultdict(list)
        for i in range(m):
            for j in range(n):
                groups[matrix[i][j]].append((i, j))

        rank_r, rank_c = [0] * m, [0] * n
        for val in sorted(groups):
            for r, c in groups[val]:
                parents[find(r)] = find(c + sep)

            roots = defaultdict(list)
            for r, c in groups[val]:
                roots[find(r)].append((r, c))

            for lst in roots.values():
                rank = max(rank_r[r] if rank_r[r] >= rank_c[c] else rank_c[c] for r, c in lst) + 1
                for r, c in lst:
                    matrix[r][c] = rank
                    rank_r[r] = rank_c[c] = rank
                    parents[r] = r
                    parents[c + sep] = c + sep
        return matrix

Explain

题解使用了并查集（Union-Find）和贪心算法来计算矩阵中每个元素的秩。首先，算法通过值将所有矩阵元素进行分组，并按照值的大小顺序处理每个分组。对于每个值，使用并查集管理行和列的关联，以确保同一行或同一列中的元素具有适当的秩关系。在处理每个值时，算法尝试将同一并查集集合中的元素秩设置为当前行和列的最大秩加一。这保证了较大元素的秩总是大于或等于与其在同一行或列的较小元素。

时间复杂度: O(m*n log(m*n))

空间复杂度: O(m*n)

class Solution:
    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:
        m, n = len(matrix), len(matrix[0]) # 矩阵的行数和列数
        sep = m + 1 if m > n else n + 1 # 设置分隔标识以区分行和列
        parents = list(range(2 * sep)) # 并查集初始化

        def find(x): # 并查集查找函数
            while x != parents[x]:
                parents[x] = x = parents[parents[x]] # 路径压缩
            return x

        groups = defaultdict(list) # 按值分组元素的坐标
        for i in range(m):
            for j in range(n):
                groups[matrix[i][j]].append((i, j)) # 分组元素

        rank_r, rank_c = [0] * m, [0] * n # 初始化行列秩数组
        for val in sorted(groups): # 按值大小处理每组元素
            for r, c in groups[val]:
                parents[find(r)] = find(c + sep) # 并查集合并

            roots = defaultdict(list) # 同一根的元素列表
            for r, c in groups[val]:
                roots[find(r)].append((r, c)) # 寻找相同根的元素

            for lst in roots.values(): # 更新秩
                rank = max(rank_r[r] if rank_r[r] >= rank_c[c] else rank_c[c] for r, c in lst) + 1 # 确定新的秩
                for r, c in lst:
                    matrix[r][c] = rank # 设置新的秩
                    rank_r[r] = rank_c[c] = rank # 更新行和列的秩
                    parents[r] = r # 重置并查集根节点
                    parents[c + sep] = c + sep
        return matrix # 返回结果矩阵

Explore

在矩阵转换秩的问题中，使用并查集来管理行和列的关联是为了确保同一行或同一列中的元素能维持适当的秩关系。并查集能够高效地处理和查询元素间的连接状态，尤其是在同一个值的元素间。通过并查集，可以快速合并同一行或列的元素，并确保这些元素的秩满足行列内的顺序约束。这样，算法可以确保任何两个在同一行或同一列的元素，其秩的设置满足题目要求的相对大小关系。

在并查集中，将行和列的标识符设置为不同的范围（使用`sep`变量区分）是为了防止行和列间的标识符冲突。在矩阵中，行的数量和列的数量可能不同，但行和列的索引都从0开始。如果不使用不同的范围来区分，行和列的标识符可能会相同，导致错误的并查集操作。通过设置不同的范围，例如使列的标识符等于列索引加上一个偏移量`sep`，可以确保行和列在并查集中被正确区分和管理。

并查集合并操作中，将行的根节点直接设置为列的根节点（或反之）的目的是为了链接同一个值的行和列，从而使得这些行和列在同一个集合中管理。这种合并有助于维持和更新行和列的秩关系，确保在同一个集合中的所有元素（即在同一行或同一列中的元素）能有一致的秩处理逻辑。通过这种方式，算法可以更简单地处理秩的更新和保证秩的一致性，特别是在处理具有相同值的多个元素时。

在计算新的秩时，优先选择行或列中较大的秩加一而不是简单地选择最大的秩，是为了确保矩阵的秩转换满足秩的递增性和一致性要求。具体来说，对于矩阵中的某个元素，其秩应该比它同行同列中所有较小值的元素的秩都要大。通过选取同一行或列中现有秩的最大值并在此基础上加一，可以保证新的秩不仅大于所有相关行和列中较小值的元素的秩，而且还保持了整个矩阵秩的递增和一致性，避免了潜在的秩冲突。