Hard
题目描述
给你一个 m x n 的矩阵，请你返回一个新的矩阵 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)
- 秩应该尽可能小。
题目保证按上述规则计算出的答案是唯一的。
示例 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]]
约束条件：
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 500
- -10^9 <= matrix[row][col] <= 10^9
解题思路
这道题的核心思路是按值排序处理，结合并查集处理相等元素。
解题思路：
按值排序：将所有元素按值从小到大排序，这样保证小的元素先处理，大的元素后处理，天然满足大小关系。
分组处理：对于相同值的元素，需要同时处理，因为它们的秩必须相同。
并查集合并：对于同一组相同值的元素，如果它们在同一行或同一列，则需要用并查集将它们连通，确保它们具有相同的秩。
秩的计算：每个连通分量的秩等于其所在行和列中已有的最大秩加1。具体来说：
- 维护每行每列的当前最大秩
- 对于一个连通分量，其秩为该分量中所有位置所在行列的最大秩的最大值加1
- 处理完一个连通分量后，更新相应行列的最大秩
实现细节：
- 使用坐标压缩将二维坐标映射为一维
- 并查集用于合并相同值且在同一行或列的元素
- 按值分组处理，确保相等元素的秩相同
时间复杂度主要来自排序和并查集操作，空间复杂度主要用于存储排序后的元素和并查集结构。
代码实现
class Solution {
public:
vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> rank(m, vector<int>(n));
vector<int> rowMax(m, 0), colMax(n, 0);
// 收集所有元素并按值排序
vector<array<int, 3>> vals;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
vals.push_back({matrix[i][j], i, j});
}
}
sort(vals.begin(), vals.end());
// 按相同值分组处理
for (int i = 0; i < vals.size(); ) {
int j = i;
while (j < vals.size() && vals[j][0] == vals[i][0]) j++;
// 处理值相同的一组元素 [i, j)
vector<int> parent(m + n);
iota(parent.begin(), parent.end(), 0);
function<int(int)> find = [&](int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
};
// 合并同行同列的元素
for (int k = i; k < j; k++) {
int r = vals[k][1], c = vals[k][2];
parent[find(r)] = find(m + c);
}
// 计算每个连通分量的秩
unordered_map<int, int> componentRank;
for (int k = i; k < j; k++) {
int r = vals[k][1], c = vals[k][2];
int root = find(r);
componentRank[root] = max(componentRank[root], max(rowMax[r], colMax[c]) + 1);
}
// 更新结果和最大秩
for (int k = i; k < j; k++) {
int r = vals[k][1], c = vals[k][2];
int root = find(r);
rank[r][c] = componentRank[root];
rowMax[r] = max(rowMax[r], rank[r][c]);
colMax[c] = max(colMax[c], rank[r][c]);
}
i = j;
}
return rank;
}
};
class Solution:
def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:
m, n = len(matrix), len(matrix[0])
rank = [[0] * n for _ in range(m)]
row_max = [0] * m
col_max = [0] * n
# 收集所有元素并按值排序
vals = []
for i in range(m):
for j in range(n):
vals.append((matrix[i][j], i, j))
vals.sort()
# 按相同值分组处理
i = 0
while i < len(vals):
j = i
while j < len(vals) and vals[j][0] == vals[i][0]:
j += 1
# 处理值相同的一组元素 [i, j)
parent = list(range(m + n))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
# 合并同行同列的元素
for k in range(i, j):
val, r, c = vals[k]
parent[find(r)] = find(m + c)
# 计算每个连通分量的秩
component_rank = {}
for k in range(i, j):
val, r, c = vals[k]
root = find(r)
if root not in component_rank:
component_rank[root] = 0
component_rank[root] = max(component_rank[root], max(row_max[r], col_max[c]) + 1)
# 更新结果和最大秩
for k in range(i, j):
val, r, c = vals[k]
root = find(r)
rank[r][c] = component_rank[root]
row_max[r] = max(row_max[r], rank[r][c])
col_max[c] = max(col_max[c], rank[r][c])
i = j
return rank
public class Solution {
public int[][] MatrixRankTransform(int[][] matrix) {
int m = matrix.Length, n = matrix[0].Length;
int[][] rank = new int[m][];
for (int i = 0; i < m; i++) {
rank[i] = new int[n];
}
int[] rowMax = new int[m];
int[] colMax = new int[n];
// 收集所有元素并按值排序
var vals = new List<(int val, int row, int col)>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
vals.Add((matrix[i][j], i, j));
}
}
vals.Sort();
// 按相同值分组处理
for (int i = 0; i < vals.Count; ) {
int j = i;
while (j < vals.Count && vals[j].val == vals[i].val) j++;
// 处理值相同的一组元素 [i, j)
int[] parent = new int[m + n];
for (int k = 0; k < m + n; k++) {
parent[k] = k;
}
int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
// 合并同行同列的元素
for (int k = i; k < j; k++) {
int r = vals[k].row, c = vals[k].col;
parent[Find(r)] = Find(m + c);
}
// 计算每个连通分量的秩
var componentRank = new Dictionary<int, int>();
for (int k = i; k < j; k++) {
int r = vals[k].row, c = vals[k].col;
int root = Find(r);
if (!componentRank.ContainsKey(root)) {
componentRank[root] = 0;
}
componentRank[root] = Math.Max(componentRank[root], Math.Max(rowMax[r], colMax[c]) + 1);
}
// 更新结果和最大秩
for (int k = i; k < j; k++) {
int r = vals[k].row, c = vals[k].col;
int root = Find(r);
rank[r][c] = componentRank[root];
rowMax[r] = Math.Max(rowMax[r], rank[r][c]);
colMax[c] = Math.Max(colMax[c], rank[r][c]);
}
i = j;
}
return rank;
}
}
var matrixRankTransform = function(matrix) {
const m = matrix.length, n = matrix[0].length;
const rank = Array.from({length: m}, () => new Array(n).fill(0));
const rowMax = new Array(m).fill(0);
const colMax = new Array(n).fill(0);
// 收集所有元素并按值排序
const vals = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
vals.push([matrix[i][j], i, j]);
}
}
vals.sort((a, b) => a[0] - b[0]);
// 按相同值分组处理
for (let i = 0; i < vals.length; ) {
let j = i;
while (j < vals.length && vals[j][0]
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(mn log(mn) + mn α(mn)) | 排序需要 O(mn log(mn))，并查集操作需要 O(mn α(mn))，其中 α 是阿克曼函数的反函数 |
| 空间复杂度 | O(mn) | 需要存储所有元素位置、并查集结构和结果矩阵 |
相关题目
. Rank Transform of an Array (Easy)
. GCD Sort of an Array (Hard)