矩阵转换后的秩【LC1632】
给你一个 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差2的 改完一个又来一个 累了 明天再改了 =(
怎么也想不到是并查集…
- 思路：
。将矩阵组成三元组{值，横坐标，纵坐标}，根据值从小到大排序，按照顺序赋予秩
- 如果当前值在同行或者同列中未出现过，那么秩为该行该列秩的最大值+1，
- 如果当前值在同行或者同列中出现过，那么这些位置的秩为这些行列中秩的最大值+1，因此需要统计每行每列秩的最大值
- 实现【并查集】
。使用TreeMap存放某个值的所有下标，key值为数值，value为动态数组存放下标，key值从小到大排序
。然后遍历TreeMap，使用并查集处理存在相同元素时的情况，将元素分为几个连通块，对于每个连通块，里面所有元素对应的秩为这些行或列的最大秩加 1。
- 首先将某个数值的所有row和col加入并查集中，列值对应的下标+m【将二维化为一维】
- 然后对于每一个连通块找到所有节点秩的最大值，记录在rank数组中，下标为该连通块的根节点序号
- 再对该连通块内每一个位置赋予结果为最大秩+1
- 最后对并查集复原
- 并查集中size属性不是必须的，可以去除
// 并查集类 class UnionFind { private int[] p;// 值 private int[] size;// 每个节点的子节点个数（包括自身） 非必须 可去除 // 初始化 public UnionFind(int n) { p = new int[n]; size = new int[n]; for (int i = 0; i < n; ++i) { p[i] = i; size[i] = 1; } } // 找到节点x的根 public int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } // 在并查集中加入a->b的根 public void union(int a, int b) { int pa = find(a), pb = find(b); if (pa != pb) { if (size[pa] > size[pb]) { p[pb] = pa; size[pa] += size[pb]; } else { p[pa] = pb; size[pb] += size[pa]; } } } // 重置并查集 public void reset(int x) { p[x] = x; size[x] = 1; } } class Solution { public int[][] matrixRankTransform(int[][] matrix) { int m = matrix.length, n = matrix[0].length; // 存放值对应的下标 TreeMap<Integer, List<int[]>> d = new TreeMap<>(); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { d.computeIfAbsent(matrix[i][j], k -> new ArrayList<>()).add(new int[] {i, j}); } } int[] rowMax = new int[m]; int[] colMax = new int[n]; int[][] ans = new int[m][n]; // 构造并查集 UnionFind uf = new UnionFind(m + n); int[] rank = new int[m + n]; // 从小到大遍历某个值的所有下标 for (var ps : d.values()) { // ps:坐标 p[0]:row p[1]:col p[1]+m:newCol【二维化一维】 // 将row->col+m这条边加入并查集 // 如果有以下三个位置的数值相同[row1,col1][row1,col2][row2,col2][row3,col3] // 那么节点row1,row2,col1+m,col2+m会有同一个根节点 // 节点row3,col3会有同一个根节点 for (var p : ps) { uf.union(p[0], p[1] + m); } // 对于每个连通块，找到里面所有元素对应的行或列的最大秩 for (var p : ps) { int i = p[0], j = p[1]; rank[uf.find(i)] = Math.max(rank[uf.find(i)], Math.max(rowMax[i], colMax[j])); } // 对于每个连通块，其秩为最大秩+1 for (var p : ps) { int i = p[0], j = p[1]; ans[i][j] = 1 + rank[uf.find(i)]; rowMax[i] = ans[i][j]; colMax[j] = ans[i][j]; } // 处理完一个连通块之后需要将并查集复原 for (var p : ps) { uf.reset(p[0]); uf.reset(p[1] + m); } } return ans; } } 作者：ylb 链接：https://leetcode.cn/problems/rank-transform-of-a-matrix/solutions/2075493/by-lcbin-ll29/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
。复杂度
- 时间复杂度：O(m×n×(logm+logn))。并查集的合并次数是O(m×n)，构建TreeMap的复杂度为 O(m×n×(logm+logn))，
- 空间复杂度：O(m×n)。并查集的空间复杂度为O(m+n)，TreeMap的空间复杂度为O(m×n)。
