并查集定义

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.__count

1. 元素值大于变化阈值的子数组

难度

• 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 -1

2. 最长连续序列

难度

• 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)