# 1632. Rank Transform of a Matrix
###### tags: `Leetcode` `Hard` `Union Find` `Union Find by Index`
Link: https://leetcode.com/problems/rank-transform-of-a-matrix/description/
## 思路
先想到我们从最小的value开始找起 因为最小的value无论如何rank都是1
接着对于下一个value要出现的row和col我们看现在最小的rank是多少 然后+1即可
但这时候可能会想到如果一个数出现在同一个col但是不同row 一个row现在最小的rank是5 一个是3 那么我们怎么解决这个问题呢
答案就是union find 对于拥有同样值的所有位置 我们把它的col和row union起来 并且每次union的时候我们把father的rank暂且设成现在最大的rank
union之后 对于在同一个group里面的所有row和col 我们把新的rank都设成father的rank(也就是整个group最大的rank)+1 并且改原matrix的rank
这里为了节省空间，在array里面我们直接用m+j表示col ```j```
## Code

class Solution {
    int[] fa;
    int[] rank2;
    public int[][] matrixRankTransform(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        TreeMap<Integer, List<int[]>> map = new TreeMap<>();
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(!map.containsKey(matrix[i][j])){
                    map.put(matrix[i][j], new ArrayList<>());
                }
                map.get(matrix[i][j]).add(new int[]{i,j});
            }
        }
        fa = new int[m+n];
        int[] rank = new int[m+n];
        for(int key:map.keySet()){
            List<int[]> list = map.get(key);
            for(int i=0; i<m+n; i++) fa[i] = i;
            rank2 = rank.clone();
            for(int[] pos:list){
                combine(pos[0], pos[1]+m);
            }
            for(int[] pos:list){
                matrix[pos[0]][pos[1]] = rank2[find(pos[0])]+1;
                rank[pos[0]] = rank2[find(pos[0])]+1;
                rank[pos[1]+m] = rank2[find(pos[0])]+1;
            }
        }
        return matrix;
    }
    private int find(int a){
        if(fa[a]==a) return a;
        else return fa[a] = find(fa[a]);
    }
    private void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return;
        fa[a] = b;
        rank2[b] = Math.max(rank2[a],rank2[b]);
    }
}