千问 LeetCode 1632.矩阵转换后的排名 public int[][] matrixRankTransform(int[][] matrix)

这道题是 LeetCode 中难度较高的题目考察了排序、贪心算法以及并查集的综合应用。 题目解析核心目标是为矩阵中的每个元素分配一个“秩”rank秩从 1 开始且需要满足以下规则1. 保序性在同一行或同一列中如果元素 p valueToPositions new TreeMap();for (int i 0; i new ArrayList()).add(new int[]{i, j});}}// 记录每行和每列当前的最大秩int[] rowMaxRank new int[m];int[] colMaxRank new int[n];int[][] result new int[m][n];// 并查集大小为 m n前 m 个代表行后 n 个代表列UnionFind uf new UnionFind(m n);// 2. 按值从小到大处理for (List positions : valueToPositions.values()) {// 3. 将当前值的所有位置通过并查集连接起来// 如果一个元素在 (r, c)就将行 r 和列 cm 连接for (int[] pos : positions) {uf.union(pos[0], pos[1] m);}// 用于存储每个连通分量的根节点到该分量内所有位置的映射Map components new HashMap();for (int[] pos : positions) {int root uf.find(pos[0]); // 行节点的根可以代表整个连通分量components.computeIfAbsent(root, k - new ArrayList()).add(pos);}// 4 5. 对每个连通分量计算秩并更新结果for (List component : components.values()) {// 找出该连通分量中所有位置对应的行和列的最大秩int maxRank 0;for (int[] pos : component) {int r pos[0];int c pos[1];maxRank Math.max(maxRank, Math.max(rowMaxRank[r], colMaxRank[c]));}// 该连通分量所有元素的秩为 maxRank 1int finalRank maxRank 1;for (int[] pos : component) {int r pos[0];int c pos[1];result[r][c] finalRank;// 更新行和列的最大秩rowMaxRank[r] finalRank;colMaxRank[c] finalRank;}}// 处理完当前值后重置并查集为下一批值做准备for (int[] pos : positions) {uf.reset(pos[0]);uf.reset(pos[1] m);}}return result;}}