2025-09-19：属性图。用go语言，给出一个大小为 n×m 的整数矩阵 properties 和一个整数 k。定义一个函

福大大架构师每日一题

发布于 2025-12-18 11:39:24

1440

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2025-09-19：属性图。用go语言，给出一个大小为 n×m 的整数矩阵 properties 和一个整数 k。

定义一个函数，用来计算两个行向量之间不同元素的交集大小（即两行中共同出现的不重复整数的个数）。

把每一行看作图中的一个顶点，若任意两行之间共有的不同整数数目不少于 k，则在对应的两个顶点之间连一条无向边。

求该无向图中连通块（连通分量）的总数，并将该数作为结果返回。

1 <= n == properties.length <= 100。

1 <= m == properties[i].length <= 100。

1 <= properties[i][j] <= 100。

1 <= k <= m。

输入： properties = [[1,2],[1,1],[3,4],[4,5],[5,6],[7,7]], k = 1。

输出： 3。

解释：

生成的图有 3 个连通分量：

题目来自力扣3493。

分步骤描述过程

1. 问题理解：
- • 给定一个 n x m 的矩阵 properties，其中每一行是一个属性集合（可能有重复元素）。
- • 我们需要将每一行视为图中的一个顶点。
- • 如果两行（即两个顶点）之间共同拥有的不同整数的个数（即交集大小）至少为 k，则在这两个顶点之间添加一条无向边。
- • 最终目标是计算图中连通分量的数量。
2. 预处理每一行：
- • 对于矩阵的每一行，我们需要去除重复元素（因为题目要求是“不同整数”的交集）。
- • 创建一个长度为 n（行数）的切片 sets，其中每个元素是一个集合（这里用 map[int]bool 实现）。
- • 遍历每一行 properties[i]，对于每个元素，将其添加到对应的集合 sets[i] 中。这样，sets[i] 就是第 i 行的不同整数集合。
3. 构建并查集（Union-Find）数据结构：
- • 初始化一个并查集 u，大小为 n（即顶点数）。初始时每个顶点自成一个连通分量，所以连通分量数 cc 为 n。
- • 并查集支持两种操作：
  - • find(x)：查找顶点 x 的根（代表元），同时进行路径压缩。
  - • merge(from, to)：合并两个顶点所在的集合（如果它们不在同一集合中），并减少连通分量计数 cc。
4. 遍历所有行对，检查条件并合并：
- • 对于每一对行 (i, j)（其中 i 从 0 到 n-1，j 从 0 到 i-1），计算它们的集合 sets[i] 和 sets[j] 的交集大小。
  - • 具体方法：遍历较小的集合（这里代码中固定遍历 sets[j]），检查每个元素是否在 sets[i] 中存在。统计存在的个数（即交集大小）。
- • 如果交集大小 cnt >= k，则调用 u.merge(i, j) 合并这两个顶点（即合并它们所在的连通分量）。
5. 返回结果：
- • 最终，并查集中的连通分量计数 u.cc 就是答案。
6. 示例分析（输入：properties = [[1,2],[1,1],[3,4],[4,5],[5,6],[7,7]], k=1）：
- • 预处理得到集合：
  - • 第0行: {1,2}
  - • 第1行: {1}
  - • 第2行: {3,4}
  - • 第3行: {4,5}
  - • 第4行: {5,6}
  - • 第5行: {7}
- • 检查行对：
  - • (0,1): 交集{1}，大小=1>=1 → 合并。
  - • (0,2): 交集为空，不合并。
  - • ...（类似检查其他对）
  - • (2,3): 交集{4}，大小=1>=1 → 合并。
  - • (3,4): 交集{5}，大小=1>=1 → 合并（因此2,3,4合并成一个连通分量）。
  - • 其他对交集大小均小于1（或为空），不合并。
- • 最终连通分量：
  - • 分量1：行0和行1（合并）
  - • 分量2：行2、3、4（合并）
  - • 分量3：行5（单独）
- • 所以输出为3。

复杂度分析

• 时间复杂度：
- • 预处理：遍历每行元素去重，每行最多 m 个元素（m<=100），所以预处理时间为 O(n*m)。
- • 遍历所有行对：共 O(n^2) 对（n<=100，所以最多10000对）。
  - • 对于每对，计算交集大小：需要遍历一个集合（大小最多为 m，即100），所以每对操作是 O(m)。
- • 因此总时间为 O(n*m + n^2 * m) = O(n^2 * m)。代入最大数值（n=100, m=100）约为100万次操作，在Go中是可接受的。
• 额外空间复杂度：
- • 存储所有集合：n 个集合，每个集合最多 m 个元素，所以空间为 O(n*m)。
- • 并查集：O(n) 的父数组。
- • 总额外空间为 O(n*m)。

Go完整代码如下：

package main

import (
    "fmt"
)

type uf struct {
    fa []int
    cc int
}

func newUnionFind(n int) uf {
    fa := make([]int, n)
    for i := range fa {
        fa[i] = i
    }
    return uf{fa, n}
}

func (u uf) find(x int) int {
    if u.fa[x] != x {
        u.fa[x] = u.find(u.fa[x])
    }
    return u.fa[x]
}

func (u *uf) merge(from, to int) {
    x, y := u.find(from), u.find(to)
    if x == y {
        return
    }
    u.fa[x] = y
    u.cc--
}

func numberOfComponents(properties [][]int, k int)int {
    sets := make([]map[int]bool, len(properties))
    for i, a := range properties {
        sets[i] = map[int]bool{}
        for _, x := range a {
            sets[i][x] = true
        }
    }

    u := newUnionFind(len(properties))
    for i, a := range sets {
        for j, b := range sets[:i] {
            cnt := 0
            for x := range b {
                if a[x] {
                    cnt++
                }
            }
            if cnt >= k {
                u.merge(i, j)
            }
        }
    }
    return u.cc
}

func main() {
    properties := [][]int{{1, 2}, {1, 1}, {3, 4}, {4, 5}, {5, 6}, {7, 7}}
    k := 1
    result := numberOfComponents(properties, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

class UF:
    def __init__(self, n):
        self.fa = list(range(n))
        self.cc = n
    
    def find(self, x):
        if self.fa[x] != x:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]
    
    def merge(self, from_, to):
        x = self.find(from_)
        y = self.find(to)
        if x == y:
            return
        self.fa[x] = y
        self.cc -= 1

def number_of_components(properties, k):
    sets = []
    for a in properties:
        sets.append(set(a))
    
    n = len(properties)
    u = UF(n)
    for i in range(n):
        a = sets[i]
        for j in range(i):
            b = sets[j]
            cnt = len(a & b)  # 计算交集大小
            if cnt >= k:
                u.merge(i, j)
                
    return u.cc

def main():
    properties = [[1, 2], [1, 1], [3, 4], [4, 5], [5, 6], [7, 7]]
    k = 1
    result = number_of_components(properties, k)
    print(result)

if __name__ == "__main__":
    main()