难度: Hard
Submission
运行时间: 100 ms
内存: 20.4 MB
class Solution:
def numIslands2(self, row: int, col: int, positions: List[List[int]]) -> List[int]:
f = list(range(row*col))
def find(x):
if f[x] != x:
f[x] = find(f[x])
return f[x]
ans = []
cnt = 0
land = [False] * len(f)
for r, c in positions:
i = r * col + c
if not land[i]:
land[i] = True
cnt += 1
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nr, nc = r + dr, c + dc
u = nr * col + nc
if row > nr > -1 < nc < col and land[u] and find(i) != find(u):
f[find(i)] = find(u)
cnt -= 1
ans.append(cnt)
return ans
Explain
此题解采用了并查集的数据结构来追踪和管理岛屿的连接状态。每个单元格都初始化为其自身的代表（自环），表示各自为独立的岛屿。遍历每个位置，若当前位置是陆地，则检查其四周的单元格。如果相邻的单元格已经是陆地，并且属于不同的集合，则通过合并这两个集合来减少岛屿数量。每合并一次，岛屿数量减一。最后，将当前的岛屿数量加入结果列表。
时间复杂度: O(m)
空间复杂度: O(row * col + m)
class Solution:
def numIslands2(self, row: int, col: int, positions: List[List[int]]) -> List[int]:
f = list(range(row*col)) # 并查集初始化，每个点代表自己
def find(x): # 并查集的查找函数
if f[x] != x:
f[x] = find(f[x]) # 路径压缩
return f[x]
ans = [] # 结果列表
cnt = 0 # 当前岛屿数量
land = [False] * len(f) # 标记陆地位置
for r, c in positions:
i = r * col + c # 计算一维索引
if not land[i]:
land[i] = True # 标记为陆地
cnt += 1 # 增加岛屿数量
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nr, nc = r + dr, c + dc
u = nr * col + nc
if row > nr > -1 < nc < col and land[u] and find(i) != find(u):
f[find(i)] = find(u) # 合并岛屿
cnt -= 1 # 更新岛屿数量
ans.append(cnt) # 记录当前岛屿数量
return ans
Explore
在并查集中，合并两个集合通常是通过将一个集合的代表节点指向另一个集合的代表节点来完成的。这种方法快速有效，但如果不加管理，确实可能会影响结构的平衡性，导致查找操作的效率下降。在最坏的情况下，这可能导致查找操作的时间复杂度接近线性。为了优化这一点，常见的改进方法包括按秩合并（合并时考虑树的大小或高度）和路径压缩（在查找时扁平化结构）。这样可以帮助保持树的高度较低，从而优化操作的效率。
在处理边界条件时，为了确保不会对数组进行越界操作，代码中添加了具体的判断条件来检查数组索引的有效性。具体来说，在检查一个单元格的相邻单元格是否为陆地时，需要确保这些相邻单元格的行号和列号都在有效的范围内。这通过条件 `row > nr > -1 < nc < col` 来实现，即确保行号 `nr` 在0和 `row-1` 之间，列号 `nc` 在0和 `col-1` 之间。这样可以防止访问无效的数组索引，避免运行时错误。
并查集数据结构将每个点初始化为自己的代表是一种通用的初始化方式，适用于大多数使用并查集的场景。这种方式简单明了，可以确保在开始处理任何合并操作之前，每个元素都是自己独立集合的代表。这为后续的合并操作提供了一个清晰的起点。虽然这种初始化方式广泛适用，但在特定情况下，如果能提前知道某些元素将属于同一集合，可以通过初始时直接将这些元素放在同一集合中来优化并查集的结构和性能。
在当前的实现中，每个位置在 `land` 数组中有一个对应的布尔标记，用来指示该位置是否已经是陆地。当一个位置在 `positions` 中多次出现时，如果该位置已经被标记为陆地，后续的出现将不会再次被计算为新岛屿。这意味着，尽管位置可能多次出现，但只有第一次将其转变为陆地时才会增加岛屿数量。因此，这种处理方式确保了岛屿数量的统计不会因为位置的重复出现而受到影响。