这次的周赛后两道都是图论的题目，可真是太让人头疼了，想破了头也没想出来，还是看了 huanglin大佬的题解 ，才算是搞懂了如何求解这道题，感谢大佬。

优化无重复元素矩阵的秩的求法

虽然我们对于矩阵的每一个位置都检查了其所在的行和所在的列，但我们需要的值只有最大的那个秩的值，那么我们不妨每次更新位置时记录当前行、列的下标，当前位置的秩值为其所在行、列的 最大值 (由于从小到大更新，后更新位置的秩必然是其所在行列的最大的秩) 。
我们可以使用两个数组 int[] rowMaxRank = new int[row]; 和 int[] colMaxRank = new int[col] 分别记录行和列中最大值的下标： rowMaxRank[i] = j 表示第i行目前(最后一次更新的)最大的秩是 matrix[i][j] 所对应的秩 。事先可以初始化两个数组的值为 -1 ，表示任意一行、一列均没有访问过。于是我们可以得到如下伪代码更新这两个数组：

for(int i = 0; i < row; i++){
    for(int j = 0; j < col; j++){
        if(rowMaxRank[i] != -1){
            //当前秩为(i , rowMaxRank[i]) 对应的秩 + 1
        if(colMaxRank[j] != -1){
            //当前秩为(colMaxRank[j] , j) 对应的秩 + 1
        rowMaxRank[i] = j;
        colMaxRank[j] = i;
不过你可能还会有疑问：二维矩阵要怎么排序呢？
虽然二维矩阵的排序我们可能不会，但是一维的肯定会呀，所以不妨直接将二维矩阵下标转换为一维矩阵，然后使用Arrays.sort()进行排序。我们可以定义一个一维的下标数组，用来存储矩阵中值对应的下标，然后对这个一维数组根据矩阵中的值进行排序即可。代码如下
int row = matrix.length, col = matrix[0].length;
Integer[] indexs = new Integer[row * col];//转换二维下标为一维，存储下标，并按照矩阵中的值大小排序
Arrays.sort(indexs, (Integer i, Integer j) -> (matrix[i / col][i % col] - matrix[j / col][j % col]));
这里使用Integer[]是因为Arrays并没有提供int类型数组的Comparator，所以使用包装类进行排序。

这样排过序之后，最小的数据的下标为index = indexs[0];，那么其对应的矩阵中的下标也就是matrix[index / col][index % col]，这样就可以对排序后的矩阵操作了。
包含重复元素的矩阵的秩
有了上边的铺垫，就可以思考怎么处理包含重复元素的矩阵了。由于题目给出了定义：
如果两个元素 p 和 q 在 同一行 或者 同一列 ，那么：

--- 如果 p < q ，那么 rank(p) < rank(q)

--- 如果 p == q ，那么 rank(p) == rank(q)

--- 如果 p > q ，那么 rank(p) > rank(q)
重复元素的秩相等，这会带来什么影响呢？考虑下边的例子

对于图上相等的两个2，上边的2是同一行同一列中的最小元素，其值理应为1，但是跟他同一列的下边的2并不是他所在行的最小值，那么为了保证相同元素的秩相等，只能将上边的2的秩变为2。

也就是说，相同的元素秩相等，使得可能较小的秩变大了，为了保证答案的正确，我们更新相同元素的秩时，必须保证其秩为同行同列中相同元素秩的最大值

那么疑问就出现了，如何保证相同元素能一起更新为最大值呢？一起？并查集的使用也就顺理成章了，使用一个 leader 下标代表所有同行同列的相同元素(这里的同行同列包含传递性，也就是相同元素构成L形也是同行同列)，求解时，他们的秩为更新过程中的最大值即可。换句话说，我们不再是更新指定位置 (i , j) 的秩，而是更新他的 leader 的秩，并取最大值，其他方面与上述无重复元素矩阵秩的求法相同。

综上所述，我们就可以得到完整代码了。
class Solution {
    int[] p;//并查集，用于合并相同大小的元素，保证相同大小的元素秩相同，且应为这些相同元素中秩的最大值
    int[] vals;//对应下标的秩的值(下标使用indexs数组中的下标值表示)
    Integer[] indexs;//转换二维下标为一维，存储下标，并按照矩阵中的值大小排序
    //默写并查集
    public int find(int x){
        if(x != p[x]) p[x] = find(p[x]);
        return p[x];
    public void union(int a, int b){
        int pa = find(a), pb = find(b);
        if(pa != pb)
            p[pb] = pa;
    public int[][] matrixRankTransform(int[][] matrix) {
        int row = matrix.length, col = matrix[0].length;
        p = new int[row * col];
        vals = new int[row * col];
        indexs = new Integer[row * col];
        //初始化indexs和并查集p
        for(int i = 0; i < row * col; i++){
            indexs[i] = i;
            p[i] = i;
        //按照矩阵中的值排序indexs
        Arrays.sort(indexs, (Integer i, Integer j) -> (matrix[i / col][i % col] - matrix[j / col][j % col]));
        /* 由于经过排序后，小的元素先考虑，如果出现更新的位置(i, j) 所在的行、列已
           经更新过，那么当前位置的秩必然大于等于已经更新过的位置的秩，因此记录
           i行，j列之前最后一次更新秩的索引，然后根据索引找到最后一次更新的秩的值
           从行列取到最大值就是(i, j)位置的秩了。*/
        int[] rowMaxRank = new int[row];//rowMaxRank[i] = j 表示第i行目前(上一次更新的)最大的秩是 matrix[i][j] 的秩
        int[] colMaxRank = new int[col];//colMaxRank[j] = i 表示第j列目前(上一次更新的)最大的秩是 matrix[i][j] 的秩
        //初始化
        Arrays.fill(rowMaxRank, -1);
        Arrays.fill(colMaxRank, -1);
        int pos = 0;//遍历矩阵的索引
        while(pos < row * col){
            int val = 1;//每个位置的秩初始值
            int idx = indexs[pos];//获得排序后，第pos位置存储的索引
            //将索引转换回矩阵的下标
            int i = idx / col;
            int j = idx % col;
            //若i行中有更新过的位置
            if(rowMaxRank[i] != -1){
                //获取最后一次更新过的下标，以及秩的值
                int k = rowMaxRank[i];
                int tmpIdx = i * col + k;
                int tmpLeader = find(tmpIdx);
                int tmpVal = vals[tmpLeader];
                //相同元素秩相等
                if(matrix[i][j] == matrix[i][k]){
                    //合并相同元素
                    union(idx, tmpIdx);
                    val = tmpVal;
                }else{
                    //当前元素大于最后一次更新的元素，那么秩也要大于tmpVal
                    val = tmpVal + 1;
            //若j列中有更新过的位置
            if(colMaxRank[j] != -1){
                //获取最后一次更新过的下标，以及秩的值
                int k = colMaxRank[j];
                int tmpIdx = k * col + j;
                int tmpLeader = find(tmpIdx);
                int tmpVal = vals[tmpLeader];
                //相同元素秩相等
                if(matrix[i][j] == matrix[k][j]){
                    //合并相同元素
                    union(idx, tmpIdx);
                    //由于在rowMaxRank[i] != -1 的条件中可能更新过了val，而我们需要的是行、列中最大的秩，故取max
                    val = Math.max(val, tmpVal);
                }else{
                    //当前元素大于最后一次更新的元素，那么秩也要大于tmpVal
                    //取max理由同上
                    val = Math.max(val, tmpVal + 1);
            //更新最大秩的索引
            rowMaxRank[i] = j;
            colMaxRank[j] = i;
            //更新当前索引位置的秩的值，由于有相同元素，故只更新当前位置leader的秩的值
            int leader = find(idx);
            vals[leader] = val;
            pos++;
        //将vals中每个元素的秩转化到二维矩阵返回
        int[][] res = new int[row][col];
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                int idx = i * col + j;
                res[i][j] = vals[find(idx)];
        return res;
代码中的注释以及开篇的讲解已经很详细了，我就不在过多赘述了。

如果文章哪里有问题还请指出，感恩相遇~~