给你一个 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
方法一：贪心 + 并查集
先考虑简化情形：没有相同的元素。那么显然最小的元素的秩为
存在相同元素时则较为复杂，假设两个相同元素同行（或同列），那么就要考虑到两个元素分别对应的行（或列）的最大秩。同时还可能出现联动，比如元素 a 和 b 同行，b 和 c 同列，那么要同时考虑这三个元素。
这种联动容易想到并查集，于是用并查集将相同元素分为几个连通块，对于每个连通块，里面所有元素对应的行或列的最大秩加
class Solution:
def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:
def find(x):
if p.setdefault(x, x) != x:
p[x] = find(p[x])
return p[x]
def union(a, b):
p[find(a)] = find(b)
m, n = len(matrix), len(matrix[0])
d = defaultdict(list)
for i, row in enumerate(matrix):
for j, v in enumerate(row):
d[v].append((i, j))
row_max = [0] * m
col_max = [0] * n
ans = [[0] * n for _ in range(m)]
for v in sorted(d):
p, rank = {}, defaultdict(int)
for i, j in d[v]:
union(i, j + 500)
for i, j in d[v]:
rank[find(i)] = max(rank[find(i)], row_max[i], col_max[j])
for i, j in d[v]:
ans[i][j] = row_max[i] = col_max[j] = 1 + rank[find(i)]
return ansclass Solution {
private Map<Integer, Integer> p = new HashMap<>();
private Map<Integer, Integer> rank = new HashMap<>();
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];
for (var e : d.entrySet()) {
int v = e.getKey();
var g = e.getValue();
p.clear();
rank.clear();
for (int[] x : g) {
union(x[0], x[1] + 500);
}
for (int[] x : g) {
int i = x[0], j = x[1];
rank.put(find(i),
Math.max(rank.getOrDefault(find(i), 0), Math.max(rowMax[i], colMax[j])));
}
for (int[] x : g) {
int i = x[0], j = x[1];
ans[i][j] = 1 + rank.getOrDefault(find(i), 0);
rowMax[i] = ans[i][j];
colMax[j] = ans[i][j];
}
}
return ans;
}
private void union(int a, int b) {
p.put(find(a), find(b));
}
private int find(int x) {
p.putIfAbsent(x, x);
if (p.get(x) != x) {
p.put(x, find(p.get(x)));
}
return p.get(x);
}
}class Solution {
public:
vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
map<int, vector<pair<int, int>>> d;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
d[matrix[i][j]].push_back({i, j});
}
}
vector<int> rowMax(m);
vector<int> colMax(n);
vector<vector<int>> ans(m, vector<int>(n));
for (auto& [v, g] : d) {
unordered_map<int, int> p;
unordered_map<int, int> rank;
for (auto [i, j] : g) {
unite(i, j + 500, p);
}
for (auto [i, j] : g) {
rank[find(i, p)] = max(rank[find(i, p)], max(rowMax[i], colMax[j]));
}
for (auto [i, j] : g) {
ans[i][j] = rowMax[i] = colMax[j] = 1 + rank[find(i, p)];
}
}
return ans;
}
void unite(int a, int b, unordered_map<int, int>& p) {
p[find(a, p)] = find(b, p);
}
int find(int x, unordered_map<int, int>& p) {
if (!p.count(x)) p[x] = x;
if (p[x] != x) p[x] = find(p[x], p);
return p[x];
}
};