并查集定义
class UF:
__fa = []
__size = []
__count = 0
def __init__(self, n: int) -> None:
self.__fa = list(range(n))
self.__size = [1 for i in range(n)]
self.__count = n
def find(self, x: int) -> int:
if self.__fa[x] != x: self.__fa[x] = self.find(self.__fa[x])
return self.__fa[x]
def union(self, x: int, y: int) -> None:
rootX = self.find(x)
rootY = self.find(y)
if rootX == rootY: return
if self.__size[rootX] <= self.__size[rootY]:
self.__fa[rootX] = rootY
self.__size[rootY] += self.__size[rootX]
else:
self.__fa[rootY] = rootX
self.__size[rootX] += self.__size[rootY]
self.__count -= 1
def isConnected(self, x: int, y: int) -> bool:
return self.find(x) == self.find(y)
def getCount(self) -> int:
return self.__count1. 元素值大于变化阈值的子数组
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
并查集运用在非图题的经典案例。
首先理解，如果子数组中最大的元素都不能满足条件，更小的也一定不满足。因此我们从大到小遍历考虑，逐个将元素加入集合中，如果当前元素加入后满足条件，那么元素中其他元素一定满足（因为都大于当前元素）。
另外， j 实际上是一个虚拟头结点，实际上不存储元素，而是作为一个并查集的“头”，存储根节点和集合大小。
代码
class Solution:
def validSubarraySize(self, nums: List[int], threshold: int) -> int:
n = len(nums)
fa = list(range(n + 1))
sz = [0] * (n + 1)
def find(x: int) -> int:
if fa[x] != x:
fa[x] = find(fa[x])
return fa[x]
for num, i in sorted(zip(nums, range(n)), reverse=True):
j = find(i + 1)
fa[i] = j
sz[j] += sz[i] + 1
if num > threshold // sz[j]: return sz[j]
return -12. 最长连续序列
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
这题用并查集有点杀鸡用牛刀的感觉。
跟上一题类似，也是用并查集维护同“类”元素。再用一个 size 数组记录集合内总元素数量。
代码
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
# 一般解法
if nums == []: return 0
nums2 = set(nums)
nums = list(nums2)
nums.sort()
n = len(nums)
ans = cnt = 1
for i in range(1, n):
if nums[i] == nums[i - 1] + 1:
cnt += 1
ans = ans if ans > cnt else cnt
else: cnt = 1
return ans
# 并查集3. 被围绕的区域
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
典型的并查集应用问题。
需要注意的是，最好手动写一下查找、合并、判断是否在同一个集内函数，而不是直接手动连接，否则容易出错。
代码
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
m, n = len(board), len(board[0])
# 多建一个dummy作为所有边缘O的父节点
fa = list(range(m * n + 1))
sz = [1 for i in range(m * n + 1)]
def find(x: int) -> int:
if fa[x] != x: fa[x] = find(fa[x])
return fa[x]
def union(x: int, y: int) -> None:
rootX = find(x)
rootY = find(y)
if rootX == rootY: return
if sz[rootX] <= sz[rootY]:
fa[rootX] = rootY
sz[rootY] += sz[rootX]
else:
fa[rootY] = rootX
sz[rootX] += sz[rootY]
def isConnected(x: int, y: int) -> bool: return find(x) == find(y)
dummy = m * n
# 将所有边缘O链接到dummy
for i in range(m):
if board[i][0] == "O": union(i * n, dummy)
if board[i][n - 1] == "O": union(i * n + n - 1, dummy)
for j in range(n):
if board[0][j] == "O": union(j, dummy)
if board[m - 1][j] == "O": union((m - 1) * n + j, dummy)
# 链接内圈O
dir = [[-1, 0], [0, -1], [1, 0], [0, 1]]
for i in range(1, m - 1):
for j in range(1, n - 1):
if board[i][j] == "O":
for newDir in dir:
newI = i + newDir[0]
newJ = j + newDir[1]
if board[newI][newJ] == "O":
union(i * n + j, newI * n + newJ)
# 修改没有链接到dummy的O
for i in range(m):
for j in range(n):
if (board[i][j] == "O") and (not isConnected(i * n + j, dummy)):
board[i][j] = "X"4. 岛屿数量
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
典型的连通性问题，可以用并查集解，算是通俗易懂。但好像DFS、BFS效率更高。
代码
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
uf = UF(m * n)
dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
for dir in dirs:
newI = i + dir[0]
newJ = j + dir[1]
if (newI >= 0 and newI < m) and (newJ >= 0 and newJ < n) and grid[newI][newJ] == "1":
uf.union(i * n + j, newI * n + newJ)
islands = set()
for i in range(m):
for j in range(n):
if grid[i][j] == "1": islands.add(uf.find(i * n + j))
return len(islands)
Comments NOTHING