啊这个题之前有看见过不过那个时候还是很早的时候没什么思路，然后就看了一眼别人的思路，原来就是一个状态空间搜索而已，就用递归写出来了，虽然感觉好像写得没有别人的简洁（见实现2）。用深度优先遍历的时间复杂度是O（MN），空间复杂度是O（MN）（我也不知道多少，如果考虑是在原先的grid上更改的话应该是O（1）？）。当然，更自然的，我们也可以使用广度优先遍历算法，如实现3所示，广度优先遍历的时间复杂度为O（MN），空间复杂度O(min(M,N))，在最欢情况下，整个网格均为陆地，队列的大小可以达到min(M,N)。
最近发现自己不太会做并查集相关的题目，在复习，然后来写一下关于这个题的新做法，即用并查集代替搜索。为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为1，则将其与相邻四个方向上的1在并查集中进行合并。最终岛屿的数量就是并查集中连通分量的数目。关于并查集相关的算法循序渐进的分别有quick-find，quick-union，weighted quick-union，weighted quick-union with path compression。quick-find时间复杂度高，就先不管了。我想首先必须要掌握weighted quick-union，如实现4所示。这样做的话算法中的操作的时间复杂度分别是initialize为N，union为lgN，connected也为lgN。接着，加上更进一步的优化，维护一个额外数组sz，来记录每个根节点对应树的节点数目，在union时比较p和q所在树的节点数目，将节点数量较少的树合并到较大的树上。然后我又在这里写了最终优化完的weighted QU with path compression（如实现3），其中再find函数里使用了路径压缩，并在rank数组上使用了按秩合并，将单次操作的时间复杂度降为了alpha(MN)，其中alpha为反阿克曼函数，当自变量在人类可观测范围内（宇宙中的粒子数量）时，函数alpha(x)的值不会超过5，因此也可以看作常数时间复杂度，另外空间复杂度为O(MN)。
最后关于优化quick-union的一点小讨论：关于树的深度，普林斯顿的algorithm课程中提出了一个结论，按照Weighted QU 中的合并方式，任意一个节点的深度不会超过lgN（以2为底），因为每个节点深度加1都需要另一个树的节点数目超过节点所属树的节点数目，因此合并后，该节点所属树的节点数目至少是原来的2倍。从初始所在树的数目为1（只有自身）到最终数目为N（全部节点都属于一棵树），最多只能有lgN次double，深度最多也只能从0增加到lgN。而路径压缩则是在每次查找根节点的时候，可以顺便将子节点的父节点修改为更上一层的节点，如父节点的父节点，这样可以使树的结构变得更扁平。
class Solution:
def numIslands1(self, grid: List[List[str]]) -> int:
self.dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
self.grid = grid
cnt = 0
self.lrow, self.lcol = len(grid), len(grid[0])
for i in range(self.lrow):
for j in range(self.lcol):
pos = (i, j)
if self.judgeIsland(pos):
cnt += 1
self.clearIsland(pos)
return cnt
def clearIsland(self, pos):
self.grid[pos[0]][pos[1]] = "0"
for d in self.dirs:
neigbour = (pos[0]+d[0], pos[1]+d[1])
if 0 <= neigbour[0] < self.lrow and 0 <= neigbour[1] < self.lcol:
if self.judgeIsland(neigbour):
self.clearIsland(neigbour)
def judgeIsland(self, pos):
return self.grid[pos[0]][pos[1]] == "1"
def numIslands2(self, grid: [[str]]) -> int:
def dfs(grid, i, j):
if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] == '0': return
grid[i][j] = '0'
dfs(grid, i + 1, j)
dfs(grid, i, j + 1)
dfs(grid, i - 1, j)
dfs(grid, i, j - 1)
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
dfs(grid, i, j)
count += 1
return count
class UnionFind:
def __init__(self, grid):
m, n = len(grid), len(grid[0])
self.count = 0
self.parent = [-1] * (m * n)
self.rank = [0] * (m * n)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
self.parent[i * n + j] = i * n + j
self.count += 1
def find(self, i):
if self.parent[i] != i:
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
def union(self, x, y):
rootx = self.find(x)
rooty = self.find(y)
if rootx != rooty:
if self.rank[rootx] < self.rank[rooty]:
rootx, rooty = rooty, rootx
self.parent[rooty] = rootx
if self.rank[rootx] == self.rank[rooty]:
self.rank[rootx] += 1
self.count -= 1
def getCount(self):
return self.count
class Solution:
def numIslands3(self, grid: List[List[str]]) -> int:
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
uf = UnionFind(grid)
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == '1':
grid[r][c] = '0'
for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == '1':
uf.union(r * nc + c, x * nc + y)
return uf.getCount()
class Solution:
def numIslands4(self, grid: List[List[str]]) -> int:
f = {}
def find(x):
f.setdefault(x, x)
if f[x] != x:
f[x] = find(f[x])
return f[x]
def union(x, y):
f[find(x)] = find(y)
if not grid:
return 0
row = len(grid)
col = len(grid[0])
for i in range(row):
for j in range(col):
if grid[i][j] == "1":
for x, y in [[-1, 0], [0, -1]]:
tmp_i = i + x
tmp_j = j + y
if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == "1":
union(tmp_i * row + tmp_j, i * row + j)
res = set()
for i in range(row):
for j in range(col):
if grid[i][j] == "1":
res.add(find(i * row + j))
return len(res)