LeetCode 题解工作台
属性图
给你一个二维整数数组 properties ，其维度为 n x m ，以及一个整数 k 。 定义一个函数 intersect(a, b) ，它返回数组 a 和 b 中 共有的不同整数的数量 。 构造一个 无向图 ，其中每个索引 i 对应 properties[i] 。如果且仅当 intersect(…
6
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们先将每个属性数组转换为一个哈希表，存储在哈希表数组 中。定义一个图 ，其中 存储了与属性数组 有边相连的属性数组的索引。 然后我们遍历所有的属性哈希表，对于每一对属性哈希表 $(i, j)$，其中 $j < i$，我们检查这两个属性哈希表中的交集元素个数是否大于等于 ，如果是，则在图 中添加一条从 到 的边，同时在图 中添加一条从 到 的边。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个二维整数数组 properties，其维度为 n x m，以及一个整数 k。
定义一个函数 intersect(a, b)，它返回数组 a 和 b 中 共有的不同整数的数量 。
构造一个 无向图，其中每个索引 i 对应 properties[i]。如果且仅当 intersect(properties[i], properties[j]) >= k（其中 i 和 j 的范围为 [0, n - 1] 且 i != j），节点 i 和节点 j 之间有一条边。
返回结果图中 连通分量 的数量。
示例 1：
输入： properties = [[1,2],[1,1],[3,4],[4,5],[5,6],[7,7]], k = 1
输出： 3
解释：
生成的图有 3 个连通分量：
示例 2：
输入： properties = [[1,2,3],[2,3,4],[4,3,5]], k = 2
输出： 1
解释：
生成的图有 1 个连通分量：
示例 3：
输入： properties = [[1,1],[1,1]], k = 2
输出： 2
解释：
intersect(properties[0], properties[1]) = 1，小于 k。因此在图中 properties[0] 和 properties[1] 之间没有边。
提示：
1 <= n == properties.length <= 1001 <= m == properties[i].length <= 1001 <= properties[i][j] <= 1001 <= k <= m
解题思路
方法一：哈希表 + DFS
我们先将每个属性数组转换为一个哈希表，存储在哈希表数组 中。定义一个图 ，其中 存储了与属性数组 有边相连的属性数组的索引。
然后我们遍历所有的属性哈希表，对于每一对属性哈希表 ，其中 ，我们检查这两个属性哈希表中的交集元素个数是否大于等于 ，如果是，则在图 中添加一条从 到 的边，同时在图 中添加一条从 到 的边。
最后，我们使用深度优先搜索计算图 的连通分量的数量。
时间复杂度 ，空间复杂度 。其中 是属性数组的长度，而 是属性数组中的元素个数。
class Solution:
def numberOfComponents(self, properties: List[List[int]], k: int) -> int:
def dfs(i: int) -> None:
vis[i] = True
for j in g[i]:
if not vis[j]:
dfs(j)
n = len(properties)
ss = list(map(set, properties))
g = [[] for _ in range(n)]
for i, s1 in enumerate(ss):
for j in range(i):
s2 = ss[j]
if len(s1 & s2) >= k:
g[i].append(j)
g[j].append(i)
ans = 0
vis = [False] * n
for i in range(n):
if not vis[i]:
dfs(i)
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ability to optimize array intersections using hash sets.
- question_mark
Familiarity with graph traversal techniques like DFS or BFS.
- question_mark
Understanding of connected components in graph theory.
常见陷阱
外企场景- error
Not optimizing the intersection calculation, leading to excessive time complexity.
- error
Missing edge cases where the intersection of two arrays is less than `k`.
- error
Incorrect graph traversal or not accounting for all connected components.
进阶变体
外企场景- arrow_right_alt
Modify the problem to use weighted edges based on the number of intersecting integers.
- arrow_right_alt
Introduce additional constraints like limiting the number of edges or nodes.
- arrow_right_alt
Extend the problem to handle directed graphs instead of undirected.