https://leetcode.com/problems/rank-transform-of-a-matrix/
对并查集的灵活运用，一个比较典型的变种！

个人解答

  1. class Solution:
  2.     def matrixRankTransform(self, mat: List[List[int]]) -> List[List[int]]:
  3.         m, n = len(mat), len(mat[0])
  5.         # get pos with same value
  6.         mp = collections.defaultdict(list)
  7.         for i in range(m):
  8.             for j in range(n):
  9.                 mp[mat[i][j]].append((i, j))
  11.         # union-find ops
  12.         def set_find(st, x):
  13.             if st[x] < 0:
  14.                 return x
  15.             st[x] = set_find(st, st[x])
  16.             return st[x]
  17.         def set_union(st, x, y):
  18.             rx = set_find(st, x)
  19.             ry = set_find(st, y)
  20.             if rx == ry:
  21.                 return
  22.             if st[rx] < st[ry]:
  23.                 st[rx] += st[ry]
  24.                 st[ry] = rx
  25.             else:
  26.                 st[ry] += st[rx]
  27.                 st[rx] = ry
  29.         # record rank of rows and cols
  30.         rank = [0] * (m + n)
  32.         res = [[0] * n for _ in range(m)]
  34.         for v in sorted(mp.keys()):
  35.             # union-find set, put rows and cols together for convinient
  36.             st = [-1] * (m + n)
  38.             # deep copy, prevent inconsistant update
  39.             rank1 = rank[:]
  41.             for x, y in mp[v]:
  42.                 # put pos with same x/y together, and calculate min valid rank
  43.                 rx = set_find(st, x)
  44.                 ry = set_find(st, y + m)
  45.                 r = max(rank1[rx], rank1[ry])
  46.                 rank1[rx] = rank1[ry] = max(rank1[rx], rank1[ry], r)
  47.                 set_union(st, rx, ry)
  49.             # update rank
  50.             for x, y in mp[v]:
  51.                 res[x][y] = rank[x] = rank[y + m] = rank1[set_find(st, x)] + 1
  52.         return res

题目分析

其实题目并不是那么直截了当地告诉你要用并查集。
题目大致有两个关键点：

  1. 贪心策略：每次找出最小的值，可以保证所赋的rank不受后边的值影响
  2. 对于相同值得处理：这是比较容易忽略的，考虑到同时满足相同的值需要有相同的rank，以及不同位置可能有不同的最小rank，需要找到满足所有位置的最小rank。而找到这些相互影响的位置是其中的关键。

这是一个很经典的问题了，找出相互关联的位置，可以BFS/DFS，类似找出连通子图数量。当然，这个问题最合理的方式还是并查集。

由于涉及行列的二维，构造集合时，可以考虑建一个m+n长度的数组，这样就可以在一个数组里表示所有的两个维度的信息了，后续查找的时候也更加方便，这是一个很有用的小技巧。

有了这个并查集的结构，其它的也就顺利成章了，找到所有相互关联的位置，确定他们的最小合理rank即可。

这道题仔细分析并不是很难，但是如何优雅而快速的写出来不是那么容易，因此，有必要记下来学习学习。