问题
Rank Transform of a Matrix Hard
Given an m x n matrix, return a new matrix answer where answer[row][col] is the rank of matrix[row][col].
The rank is an integer that represents how large an element is compared to other elements. It is calculated using the following rules:
-
The rank is an integer starting from
1. -
If two elements
pandqare in the same row or column, then:- If
p < qthenrank(p) < rank(q) - If
p == qthenrank(p) == rank(q) - If
p > qthenrank(p) > rank(q)
- If
-
The rank should be as small as possible.
It is guaranteed that answer is unique under the given rules.
Example 1:
Input: matrix = [[1,2],[3,4]]
Output: [[1,2],[2,3]]
Explanation:
The rank of matrix[0][0] is 1 because it is the smallest integer in its row and column.
The rank of matrix[0][1] is 2 because matrix[0][1] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][0] is 2 because matrix[1][0] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][1] is 3 because matrix[1][1] > matrix[0][1], matrix[1][1] > matrix[1][0], and both matrix[0][1] and matrix[1][0] are rank 2.
复制代码Example 2:
Input: matrix = [[7,7],[7,7]]
Output: [[1,1],[1,1]]
复制代码Example 3:
Input: matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]
Output: [[4,2,3],[1,3,4],[5,1,6],[1,3,4]]
复制代码Example 4:
Input: matrix = [[7,3,6],[1,4,5],[9,8,2]]
Output: [[5,1,4],[1,2,3],[6,3,1]]
复制代码
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 500-109 <= matrix[row][col] <= 109
Hint 1
Sort the cells by value and process them in increasing order.
Hint 2
The rank of a cell is the maximum rank in its row and column plus one.
Hint 3
Handle the equal cells by treating them as components using a union-find data structure.
解题思路
本题看似简单，其实是一道高难度的题。求的是矩阵的秩，通俗讲就是排位，难点在于：
- 行列中的排位会互相影响，比如
p在该行中排第3，但在列中排第4，那么最终的排位是4 - 同行列中的同值节点，排位必须相同，这会影响到多行多列的排位，比如
[3,2], [3,4], [5,4]的节点值相同，那么第3行，第5行，第2列，第4列的排位会互相影响
好在LeetCode为我们准备了三个锦囊妙计，不妨拆开看一下，作为解题的线索。
Hint 1
Sort the cells by value and process them in increasing order.
第一个锦囊是让我们将所有的节点排序，然后按照从小的大的顺序处理。这样做的好处就是，在前面处理过的较小的节点，不再受到后面节点的影响。我们可以将每个节点转换为一个数据结构或者数组，比如int[3]，其中[0]表示节点的值，[1]表示行，[2]表示列。整个矩阵可以转换为int[][] arr = new int[m*n][3]。这样就可以排序，然后按照从小的大的顺序处理。
Hint 2
The rank of a cell is the maximum rank in its row and column plus one.
第二个锦囊是让我们在按照上述的顺序处理时，记录下当前行、列的最大排位，对应节点的排位就是当前行、列的最大排位中较大者+1。当然，处理完毕后，该节点的排位也要作为对应行列的最大排位。我们可以用int[] currRankRows 和int[] currRankCols来记录当前所有行列的最大排位。
Hint 3
Handle the equal cells by treating them as components using a union-find data structure.
第三个锦囊是让我们用并查集来处理同值节点。并查集被认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：
- 合并（Union）：把两个不相交的集合合并为一个集合。
- 查询（Find）：查询两个元素是否在同一个集合中。
这个锦囊可以用来解决我们前面提到的本题的难点，也就是如何处理行列之间的互相影响。我们可以将行和列视为同一类元素，将受同值节点影响的行列分到同一组，再统一组内的排位（因为同行列中的同值节点，排位必须相同）。于是我们定义
为一个并查集，用x表示一行或一列。对于矩阵中的一个元素matrix[i][j]，当x表示行时，x = i；当x表示列时，x = m + j，其中m是矩阵总行数。根据并查集的定义，
指向x的父节点，而对于根节点
。
参考答案
class Solution {
int[] f; // union-find set
public int[][] matrixRankTransform(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] ret = new int[m][n];
int[] currRankRows = new int[m];
int[] currRankCols = new int[n];
// initial union-find data structure, contains all the rows & cols, the length is m + n
int[] initF = new int[m + n];
for (int i = 0; i < m + n; i++) {
initF[i] = i;
}
// put all cells into an array then sort
int[][] arr = new int[m*n][3];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
arr[i*n+j][0] = matrix[i][j];
arr[i*n+j][1] = i;
arr[i*n+j][2] = j;
}
}
Arrays.sort(arr, Comparator.comparingInt(o->o[0]));
int i = 0;
// loop the array with all matrix cells
while(i < arr.length) {
int target = arr[i][0];
List<int[]> equals = new ArrayList<>();
// get cells that has same value
while (i < arr.length && target == arr[i][0]) {
equals.add(arr[i]);
i++;
}
// Union-find data structure
f = initF.clone();
// union set for f(x)
for (int[] cell : equals) {
union(cell[1], cell[2] + m);
}
// if equal numbers in same row/col, then group into map by f(x), as these need to have same rank
Map<Integer, List<int[]>> map = new HashMap<>();
for (int[] cell : equals) {
int k = find(cell[1]);
if (!map.containsKey(k)) {
map.put(k, new ArrayList<>());
}
map.get(k).add(cell);
}
// handle group by group
for (List<int[]> group : map.values()) {
// find max rank in group
int maxRank = 0;
for (int[] cell : group) {
int row = cell[1];
int col = cell[2];
maxRank = Math.max(maxRank, Math.max(currRankRows[row], currRankCols[col]) + 1);
}
// update max rank to current rank of rows & cols
for (int[] cell : group) {
int row = cell[1];
int col = cell[2];
ret[row][col] = maxRank;
currRankRows[row] = Math.max(currRankRows[row], maxRank);
currRankCols[col] = Math.max(currRankCols[col], maxRank);
}
}
}
return ret;
}
int find (int x) {
if (f[x] != x) {
f[x] = find(f[x]);
}
return f[x];
}
void union(int x, int y) {
int fm = find(x);
int fn = find(y);
f[fm] = fn;
}
}
复制代码拓展训练
到作者的LeetCode专栏中看看，有没有其他感兴趣的问题吧！
近期评论