HardRating 2530

1632. Rank Transform of a Matrix

arrayunion-findgraphtopological-sortsortingmatrix

在 LeetCode 上作答 ↗

解題說明

Rank Transform of a Matrix

題目描述：給定一個 m × n 矩陣 matrix，將每個元素替換為它的「排名」。排名規則：(1) 排名從 1 開始；(2) 較小的元素排名較小；(3) 同一行或同一列的兩個相等元素必須有相同排名；(4) 排名盡可能小。

解題思路：將所有元素按值分組排序。從小到大處理每組：同一組中同行或同列的元素需要相同排名，用並查集將它們合併。對於每個合併後的集合，其排名等於集合中所有元素所在行和列的當前最大排名 + 1。處理完一組後更新各行各列的最大排名。

C++ 解法

複雜度分析

時間複雜度：O(m × n × log(m × n) × alpha(m + n)) — 排序所有元素 O(mn log(mn))，並查集操作幾乎為常數

空間複雜度：O(m × n + m + n) — 分組儲存、結果矩陣、行列最大排名

虛擬碼

1. Group all cells by their value, sorted ascending
2. Initialize rowMax[m] = 0, colMax[n] = 0
3. For each value group (ascending order):
   a. Create Union-Find for (m + n) nodes (rows 0..m-1, cols m..m+n-1)
   b. For each cell (r, c) in group, unite(r, m+c)
   c. For each connected component, rank = max(rowMax[r]+1, colMax[c]+1) over all (r,c) in component
   d. Assign rank to all cells in component
   e. Update rowMax and colMax
4. Return result matrix

其他解法

方法二：拓撲排序 建立有向圖：對於同行或同列中值不同的元素，較小的指向較大的。用拓撲排序分層確定排名。但相等元素的處理仍需並查集。時間複雜度 O(m^2 n + mn^2) 建圖，通常較慢。

方法三：貪心 + 逐行逐列處理 先對每行和每列內部排序，再嘗試合併排名。但跨行列的依賴關係使此法容易出錯，必須謹慎處理。

延伸思考

如果矩陣中沒有重複元素，問題會如何簡化？還需要並查集嗎？
如果排名規則改為「不同行列中相等的元素也必須有相同排名」，解法需要如何修改？
這道題和 LeetCode 1331（Rank Transform of an Array）相比，核心難點在哪裡？

Rank Transform of a Matrix — CaffeCode