我工资6000，新来的8000，知道后和老板大吵一架，辞职去了别的公司月薪 1w。但昨天老板给我打电话，让我回去解决一个问题。。
程
老鬼约 5 分钟
老鬼约 5 分钟兄弟们，这事儿搁谁身上能不气？
原来工资6000，新来的8000，换你你也得炸毛！不过这位老哥倒是挺刚，直接和老板吵了一架，甩手走人，找了个新公司工资翻了快一倍💰。
可妙就妙在，昨天老板居然又打电话来了，要请他回去解决个问题……咋的？想起来我有用了？
作为一个老码农，我太懂这种感觉了—— 当初你爱答不理，现在我让你高攀不起 。
程序员这个圈子就是这样，值钱的是能力，不是人情。如果老板诚心诚意，价码够高，那咱就谈谈，但如果只是想白嫖，那就请他 尊重市场行情 。
所以啊，大家记住，跳槽不是错，关键是涨薪！如果回去还能狠狠赚一笔，那为什么不呢？ 代码无情，但钱包最诚实。 【备注:文末可领最新资料】 。
算法题： 矩阵转换后的秩
矩阵转换后的秩这个题目，刚看到的时候，感觉就是个 标准的数学问题 ，但实际上，考察的东西还挺多，涉及 拓扑排序、并查集 等概念，做起来比一般的矩阵问题烧脑多了。 题目大致意思是这样的：给你一个
m x n
的矩阵
matrix
，你需要返回**相同形状的矩阵
rank
**，其中
rank[i][j]
表示
matrix[i][j]
在转换后得到的秩（rank）。计算规则如下：
- 秩从 1 开始 ，如果某个元素比另一个元素大，它的秩不能比后者小。
- 行和列都要保持非递减性 ，即某个元素的秩不能小于它 所在行和所在列中比它小的元素的秩 。
- 相同的值必须要有相同的秩 。
“老板给你一个Excel表格，说：我要按数值大小排序，同时保证行和列的顺序不变，你来搞定。”
你敢信？要是用暴力方法，那就是
O(n^3)
甚至更高的复杂度，
性能感人
。
思路
看到这个题目，最直觉的想法是： 先排序，再做动态规划 。但是这题有个坑点，就是 相同的值必须要有相同的秩 ，这就需要一个更巧妙的处理方式：
- 先把所有元素 按数值大小排序 ，然后 从小到大依次处理 。
- 并查集 可以用来连接所有相等的元素，确保它们的秩相同。
- 拓扑排序 的思维来保证行列的秩递增性。
OK，直接看代码：
import java.util.*;
public class MatrixRankTransform {
public int[][] matrixRankTransform(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] rank = new int[m][n];
// 存储坐标值
Map<Integer, List<int[]>> valueToCells = new TreeMap<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
valueToCells.computeIfAbsent(matrix[i][j], v -> new ArrayList<>()).add(new int[]{i, j});
}
}
int[] rowMax = new int[m]; // 记录每一行的最大秩
int[] colMax = new int[n]; // 记录每一列的最大秩
// 按照数值大小依次处理
for (List<int[]> cells : valueToCells.values()) {
UnionFind uf = new UnionFind(m + n);
Map<Integer, List<Integer>> groupMap = new HashMap<>();
// 先做并查集合并，同值的点相连
for (int[] cell : cells) {
int x = cell[0], y = cell[1] + m;
uf.union(x, y);
}
// 根据并查集的根节点，构建分组
for (int[] cell : cells) {
int root = uf.find(cell[0]);
groupMap.computeIfAbsent(root, v -> new ArrayList<>()).add(cell[0] * n + cell[1]);
}
// 计算每个组的秩
for (List<Integer> group : groupMap.values()) {
int maxRank = 0;
for (int pos : group) {
int i = pos / n, j = pos % n;
maxRank = Math.max(maxRank, Math.max(rowMax[i], colMax[j]) + 1);
}
for (int pos : group) {
int i = pos / n, j = pos % n;
rank[i][j] = maxRank;
rowMax[i] = maxRank;
colMax[j] = maxRank;
}
}
}
return rank;
}
static class UnionFind {
int[] parent;
UnionFind(int size) {
parent = new int[size];
for (int i = 0; i < size; i++) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void union(int x, int y) {
parent[find(x)] = find(y);
}
}
public static void main(String[] args) {
MatrixRankTransform sol = new MatrixRankTransform();
int[][] matrix = {
{1, 2},
{3, 4}
};
int[][] result = sol.matrixRankTransform(matrix);
for (int[] row : result) {
System.out.println(Arrays.toString(row));
}
}
}
代码解读
这段代码主要做了几个关键步骤：
- 先按数值排序 ，确保从最小值开始处理。
- 并查集 用于连接相等的元素，保证相同的值有相同的秩。
-
用
rowMax和colMax记录当前行、列的最大秩 ，确保递增性。 - 拓扑排序思维 ：小的值先处理，秩依次递增。
复杂度分析
-
排序部分
：
O(mn log(mn)) -
并查集部分
：均摊
O(α(mn))，几乎是O(1) -
遍历赋值部分
：
O(mn)
O(n^3)
香太多
😆。
总结
这个题说白了就是 动态规划+拓扑排序+并查集的结合 ，不是简单的暴力枚举能解决的。当你遇到 既要满足局部递增，又要满足全局约束 的题目， 并查集+拓扑排序 往往是解法之一。 代码虽然有点绕，但捋清逻辑后，其实还挺直观： 按值从小到大遍历，合并相同值，最后保证递增性 。
写出来还是蛮有成就感的，毕竟这种题不仅考察代码能力，还考察对数据结构的掌握程度。
写完了，我想起了一句话：
算法写得好，绩效少不了；代码写得烂，年终两行泪。愿大家都能在算法的世界里 少踩坑，多涨薪 ！
最后，我为大家打造了一份deepseek的入门到精通教程，完全免费： https://www.songshuhezi.com/deepseek
也可以看我写的这篇文章《 DeepSeek满血复活，直接起飞！ 》来进行本地搭建。
-END -
ok，今天先说到这，老规矩，给大家分享一份不错的副业资料，感兴趣的同学可以链 接我，微信： hls404 找 我领取。 以上，就是今天的分享了， 看完文章记得右下角点赞，也欢迎在评论区写下你的留言 。