矩阵转换后的秩
难度:
标签:
题目描述
给你一个 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.lengthn == matrix[i].length1 <= m, n <= 500-109 <= matrix[row][col] <= 109
代码结果
运行时间: 383 ms, 内存: 63.6 MB
/*
* 思路：
* 1. 使用流来将矩阵中的所有元素按值从小到大排序。
* 2. 使用并查集跟踪元素所在行和列的最大秩。
* 3. 对于每个元素，计算其秩，更新并查集。
* 4. 最后，返回计算好的秩矩阵。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int[][] matrixRankTransform(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] answer = new int[m][n];
List<int[]> elements = IntStream.range(0, m)
.boxed()
.flatMap(i -> IntStream.range(0, n)
.mapToObj(j -> new int[]{matrix[i][j], i, j}))
.sorted(Comparator.comparingInt(a -> a[0]))
.collect(Collectors.toList());
int[] rowMaxRank = new int[m];
int[] colMaxRank = new int[n];
Arrays.fill(rowMaxRank, 0);
Arrays.fill(colMaxRank, 0);
elements.forEach(element -> {
int value = element[0], row = element[1], col = element[2];
int currentRank = Math.max(rowMaxRank[row], colMaxRank[col]) + 1;
answer[row][col] = currentRank;
rowMaxRank[row] = currentRank;
colMaxRank[col] = currentRank;
});
return answer;
}
}
解释
方法:
题解使用了并查集（Union-Find）和贪心算法来计算矩阵中每个元素的秩。首先，算法通过值将所有矩阵元素进行分组，并按照值的大小顺序处理每个分组。对于每个值，使用并查集管理行和列的关联，以确保同一行或同一列中的元素具有适当的秩关系。在处理每个值时，算法尝试将同一并查集集合中的元素秩设置为当前行和列的最大秩加一。这保证了较大元素的秩总是大于或等于与其在同一行或列的较小元素。
时间复杂度:
O(m*n log(m*n))
空间复杂度:
O(m*n)
代码细节讲解
🦆
为什么在处理每个值时，需要使用并查集来管理行和列的关联？
▷🦆
在并查集中，为什么选择将行和列的标识符设置为不同的范围，比如使用`sep`变量区分？
▷🦆
并查集合并操作中，将行的根节点直接设置为列的根节点（或反之）有什么具体的目的或好处？
▷🦆
在计算新的秩时，为什么优先选择行或列中较大的秩加一，而不是简单地选择最大的秩？
▷