矩阵转换后的秩

题目

1632. 矩阵转换后的秩

---

给你一个 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.length
• n == matrix[i].length
• 1 <= m, n <= 500
• -10^9 <= matrix[row][col] <= 10^9

题解

方法一：

思路

对于同一行同一列相同的数排名相同。
我们同行同列的相同值用并查集连接。

然后类似拓扑排序：
只需要将矩阵中元素下标按照元素值由小到大排序。
记录每一行每一列最近访问的位置。最近访问的位置与当前位置值不同则存在一条边。

用并查集根节点的记录排名。
最后对于每个节点的排名用并查集找根节点的排名即可。

代码

class Solution {
public:
    const int NINF = 0xf3f3f3f3;
    vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();

        //元素坐标按元素值升序排序
        vector<pair<int,int>> idx;
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                idx.emplace_back(i,j);
            }
        }
        sort(idx.begin(), idx.end(), [&](auto& a, auto& b) {
            return matrix[a.first][a.second] < matrix[b.first][b.second];
        });
        //dsu 
        int st[1000000];
        memset(st, -1, sizeof(st));
        function<int(int)> ufind = [&](int x) {
            return st[x]<0?x:st[x]=ufind(st[x]);
        };
        auto enc = [](int x,int y) {
            return x*1000+y;
        };
        //行/列相同元素值，用并查集将下标纳入同一个集合
        for (int i=0; i<n; i++) {
            unordered_map<int,pair<int,int>> mp;
            for (int j=0; j<m; j++) {
                if (mp.count(matrix[i][j])) {
                    auto [x,y] = mp[matrix[i][j]];
                    int fx = ufind(enc(x,y)), fy = ufind(enc(i,j));
                    if (fx == fy) continue;
                    st[fy] = fx;
                }
                mp[matrix[i][j]] = {i,j};
            }
        }
        for (int i=0; i<m; i++) {
            unordered_map<int,pair<int,int>> mp;
            for (int j=0; j<n; j++) {
                if (mp.count(matrix[j][i])) {
                    auto [x,y] = mp[matrix[j][i]];
                    int fx = ufind(enc(x,y)), fy = ufind(enc(j,i));
                    if (fx == fy) continue;
                    st[fy] = fx;
                }
                mp[matrix[j][i]] = {j,i};
            }
        }

        vector<pair<int,int>> r(n,{-1,-1}), c(m, {-1,-1});//行/列最近访问元素
        for (auto [i,j]:idx) {
            auto [x1, y1] = r[i];
            auto [x2, y2] = c[j];
            if (x1 != -1 && matrix[x1][y1] != matrix[i][j]) {
                int v = max(-st[ufind(enc(x1,y1))]+1, -st[ufind(enc(i,j))]);
                st[ufind(enc(i,j))] = -v;
            }
            if (x2 != -1 && matrix[x2][y2] != matrix[i][j]) {
                int v = max(-st[ufind(enc(x2,y2))]+1, -st[ufind(enc(i,j))]);
                st[ufind(enc(i,j))] = -v;
            }
            r[i] = c[j] = {i,j};
        }
        vector<vector<int>> ans(n, vector<int>(m));
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                ans[i][j] = -st[ufind(enc(i,j))];
            }
        }
        return ans;
    }
};