HardRating 1885

305. Number of Islands II

arrayhash-tableunion-findmatrix

解題說明

Number of Islands II

題目描述：給定一個 m × n 的全水網格，依序執行一系列 addLand(r, c) 操作，每次將 (r, c) 格子從水變成陸地。回傳一個陣列，記錄每次操作後當前的島嶼數量。兩個格子若上下左右相鄰且都是陸地，則屬於同一座島嶼。

解題思路：

此題的核心在於動態連通性：每次新增陸地後，需要快速更新島嶼計數。Union-Find（並查集）天生適合此場景。

節點編碼：用 r * cols + c 將二維座標壓縮為一維節點 ID，方便作為並查集的索引。
初始化：parent[] 和 rank[] 陣列，初始所有格子為未啟用（可用 -1 標記）。維護一個 islandCount 計數器。
每次 addLand(r, c)：
- 若該格已是陸地（重複操作），直接加入當前計數後繼續。
- 否則將格子啟用，islandCount++（暫時視為孤立島嶼）。
- 檢查上下左右四個相鄰格：若相鄰格是陸地且與當前格不同連通分量，執行 union 操作，islandCount--。
Union-Find 模板：使用路徑壓縮（find 中遞迴更新 parent）與按秩合併（union 時比較 rank），使每次操作近乎 O(α(n)) — 逆阿克曼函數，實用上視為常數。

這樣每次 addLand 的均攤時間複雜度接近 O(1)，整體處理 k 次操作為 O(k · α(m*n))。

C++ 解法

複雜度分析

時間複雜度：O(k · α(m·n))，其中 k 為操作次數，α 為逆阿克曼函數。路徑壓縮 + 按秩合併使每次 find/union 均攤 O(α(n))，實務上視為常數，整體接近 O(k)。

空間複雜度：O(m·n) — 儲存 parent 和 rank 兩個長度為 m·n 的陣列。輸出結果陣列 O(k) 另計。

虛擬碼

1. Initialize parent[] = -1 (water), rank[] = 0, islandCount = 0
2. For each position (r, c) in positions:
   a. Compute id = r * cols + c
   b. If parent[id] != -1 (duplicate): append islandCount to result, continue
   c. Set parent[id] = id, islandCount++
   d. For each of 4 directions (nr, nc):
      - Skip if out of bounds
      - nid = nr * cols + nc
      - If parent[nid] == -1: skip (water)
      - Else: unite(id, nid) which decrements islandCount if roots differ
   e. Append islandCount to result
3. Return result

find(x):
  If parent[x] != x: parent[x] = find(parent[x])  // path compression
  Return parent[x]

unite(a, b):
  a = find(a), b = find(b)
  If a == b: return
  Merge smaller rank under larger; islandCount--

其他解法

BFS/DFS 暴力重算 O(k · m·n)：每次 addLand 後重新從頭 BFS/DFS 計算所有島嶼。優點是實作直觀，缺點是每次操作都要掃描整個網格，k 次操作總時間為 O(k·m·n)，當 k 與 m·n 都很大時效率極差，無法通過本題。

雜湊表版 Union-Find（稀疏優化）：當 positions 數量遠小於 m·n 時，可用 unordered_map<int,int> 代替固定大小陣列作為 parent，只為實際出現的陸地節點分配空間。優點是節省記憶體（從 O(m·n) 降至 O(k)），缺點是雜湊表常數較大，在 k 與 m·n 相近時不如陣列版本。

離線排序（Kruskal 思路）：若可以離線處理，將所有 addLand 操作一次讀入，再按時間順序建圖並用 Kruskal 合併。優點是可以利用邊排序的性質做進一步最佳化，但不支援在線查詢，且不適用本題的即時回傳需求。

延伸思考

若 addLand 操作可以改為 removeLand（將陸地變回水），Union-Find 不支援分裂操作，該如何處理？（提示：考慮離線 + 逆向 Union-Find）
若網格極大（例如 10⁹ × 10⁹），但操作次數 k 很少，如何修改資料結構使空間從 O(m·n) 降至 O(k)？
本題中如何偵測並正確處理重複的 addLand 操作（同一格加陸地多次）？對計數結果有何影響？

解題說明

Number of Islands II

解題思路：

此題的核心在於動態連通性：每次新增陸地後，需要快速更新島嶼計數。Union-Find（並查集）天生適合此場景。

節點編碼：用 r * cols + c 將二維座標壓縮為一維節點 ID，方便作為並查集的索引。
初始化：parent[] 和 rank[] 陣列，初始所有格子為未啟用（可用 -1 標記）。維護一個 islandCount 計數器。
每次 addLand(r, c)：
- 若該格已是陸地（重複操作），直接加入當前計數後繼續。
- 否則將格子啟用，islandCount++（暫時視為孤立島嶼）。
- 檢查上下左右四個相鄰格：若相鄰格是陸地且與當前格不同連通分量，執行 union 操作，islandCount--。
Union-Find 模板：使用路徑壓縮（find 中遞迴更新 parent）與按秩合併（union 時比較 rank），使每次操作近乎 O(α(n)) — 逆阿克曼函數，實用上視為常數。

這樣每次 addLand 的均攤時間複雜度接近 O(1)，整體處理 k 次操作為 O(k · α(m*n))。

複雜度分析

空間複雜度：O(m·n) — 儲存 parent 和 rank 兩個長度為 m·n 的陣列。輸出結果陣列 O(k) 另計。

虛擬碼

1. Initialize parent[] = -1 (water), rank[] = 0, islandCount = 0 2. For each position (r, c) in positions: a. Compute id = r * cols + c b. If parent[id] != -1 (duplicate): append islandCount to result, continue c. Set parent[id] = id, islandCount++ d. For each of 4 directions (nr, nc): - Skip if out of bounds - nid = nr * cols + nc - If parent[nid] == -1: skip (water) - Else: unite(id, nid) which decrements islandCount if roots differ e. Append islandCount to result 3. Return result find(x): If parent[x] != x: parent[x] = find(parent[x]) // path compression Return parent[x] unite(a, b): a = find(a), b = find(b) If a == b: return Merge smaller rank under larger; islandCount--

其他解法

延伸思考

若 addLand 操作可以改為 removeLand（將陸地變回水），Union-Find 不支援分裂操作，該如何處理？（提示：考慮離線 + 逆向 Union-Find）
若網格極大（例如 10⁹ × 10⁹），但操作次數 k 很少，如何修改資料結構使空間從 O(m·n) 降至 O(k)？
本題中如何偵測並正確處理重複的 addLand 操作（同一格加陸地多次）？對計數結果有何影響？