Given an m x n
matrix
, return a new matrix answer
where answer[row][col]
is the rank of matrix[row][col]
.
The rank is an integer that represents how large an element is compared to other elements. It is calculated using the following rules:
- The rank is an integer starting from
1
. - If two elements
p
andq
are in the same row or column, then:- If
p < q
thenrank(p) < rank(q)
- If
p == q
thenrank(p) == rank(q)
- If
p > q
thenrank(p) > rank(q)
- If
- The rank should be as small as possible.
It is guaranteed that answer
is unique under the given rules.
Example 1:
Input: matrix = [[1,2],[3,4]] Output: [[1,2],[2,3]] Explanation: The rank of matrix[0][0] is 1 because it is the smallest integer in its row and column. The rank of matrix[0][1] is 2 because matrix[0][1] > matrix[0][0] and matrix[0][0] is rank 1. The rank of matrix[1][0] is 2 because matrix[1][0] > matrix[0][0] and matrix[0][0] is rank 1. The rank of matrix[1][1] is 3 because matrix[1][1] > matrix[0][1], matrix[1][1] > matrix[1][0], and both matrix[0][1] and matrix[1][0] are rank 2.
Example 2:
Input: matrix = [[7,7],[7,7]] Output: [[1,1],[1,1]]
Example 3:
Input: matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]] Output: [[4,2,3],[1,3,4],[5,1,6],[1,3,4]]
Example 4:
Input: matrix = [[7,3,6],[1,4,5],[9,8,2]] Output: [[5,1,4],[1,2,3],[6,3,1]]
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 500
-109 <= matrix[row][col] <= 109
Solution: Union Find
Group cells by their values, process groups (cells that have the same value) in ascending order (smaller number has smaller rank).
For cells that are in the same row and same cols union them using union find, they should have the same rank which equals to max(max_rank_x[cols], max_rank_y[rows]) + 1.
Time complexity: O(m*n*(m+n))
Space complexity: O(m*n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
// Author: Huahua class DSU { public: DSU(int n): p_(n, -1) {} int find(int x) { return p_[x] == -1 ? x : p_[x] = find(p_[x]); } void merge(int x, int y) { x = find(x), y = find(y); if (x != y) p_[x] = y; } private: vector<int> p_; }; class Solution { public: vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) { const int m = matrix.size(); const int n = matrix[0].size(); vector<vector<int>> ans(m, vector<int>(n)); map<int, vector<pair<int, int>>> mp; // val -> {positions} for (int y = 0; y < m; ++y) for (int x = 0; x < n; ++x) mp[matrix[y][x]].emplace_back(x, y); vector<int> rx(n), ry(m); for (const auto& [val, ps]: mp) { DSU dsu(n + m); vector<vector<pair<int, int>>> cc(n + m); // val -> {positions} for (const auto& [x, y]: ps) dsu.merge(x, y + n); for (const auto& [x, y]: ps) cc[dsu.find(x)].emplace_back(x, y); for (const auto& ps: cc) { int rank = 1; for (const auto& [x, y]: ps) rank = max(rank, max(rx[x], ry[y]) + 1); for (const auto& [x, y]: ps) rx[x] = ry[y] = ans[y][x] = rank; } } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment