Medium

题目描述

给你一个大小为 n x m 的二维整数数组 properties 和一个整数 k。

定义一个函数 intersect(a, b)，返回数组 a 和 b 中共同的不同整数的数量。

构造一个无向图，其中每个索引 i 对应 properties[i]。当且仅当 intersect(properties[i], properties[j]) >= k 时，节点 i 和节点 j 之间存在一条边，其中 i 和 j 在范围 [0, n - 1] 内且 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 <= 100
  • 1 <= m == properties[i].length <= 100
  • 1 <= properties[i][j] <= 100
  • 1 <= k <= m

解题思路

这道题要求构建一个图，并计算其连通分量的数量。解题思路如下：

  1. 构建图的邻接关系：遍历所有节点对 (i, j)，计算 properties[i] 和 properties[j] 的交集大小。如果交集大小 >= k，则在节点 i 和 j 之间建立边。

  2. 计算交集：对于两个数组的交集，可以使用集合运算。将数组转换为集合，然后计算两个集合的交集大小。

  3. 寻找连通分量：可以使用以下三种方法之一：

    • DFS（深度优先搜索）：从每个未访问的节点开始进行 DFS，每次 DFS 找到一个连通分量
    • BFS（广度优先搜索）：类似 DFS，使用队列进行层序遍历
    • 并查集（Union-Find）：将有边连接的节点合并到同一个集合中，最后统计集合数量

推荐使用 DFS 方法，因为它实现简单且效率较高。算法步骤：

  • 首先构建邻接表表示图
  • 使用 visited 数组记录已访问的节点
  • 对每个未访问的节点进行 DFS，每次 DFS 代表找到一个新的连通分量

代码实现

class Solution {
public:
    int numberOfComponents(vector<vector<int>>& properties, int k) {
        int n = properties.size();
        vector<vector<int>> graph(n);
        
        // 构建图
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (intersect(properties[i], properties[j]) >= k) {
                    graph[i].push_back(j);
                    graph[j].push_back(i);
                }
            }
        }
        
        // DFS 寻找连通分量
        vector<bool> visited(n, false);
        int components = 0;
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(graph, visited, i);
                components++;
            }
        }
        
        return components;
    }
    
private:
    int intersect(const vector<int>& a, const vector<int>& b) {
        unordered_set<int> setA(a.begin(), a.end());
        int count = 0;
        for (int val : b) {
            if (setA.count(val)) {
                count++;
                setA.erase(val);  // 避免重复计数
            }
        }
        return count;
    }
    
    void dfs(const vector<vector<int>>& graph, vector<bool>& visited, int node) {
        visited[node] = true;
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                dfs(graph, visited, neighbor);
            }
        }
    }
};

class Solution:
    def numberOfComponents(self, properties: List[List[int]], k: int) -> int:
        n = len(properties)
        
        # 构建图
        graph = [[] for _ in range(n)]
        for i in range(n):
            for j in range(i + 1, n):
                if self.intersect(properties[i], properties[j]) >= k:
                    graph[i].append(j)
                    graph[j].append(i)
        
        # DFS 寻找连通分量
        visited = [False] * n
        components = 0
        
        for i in range(n):
            if not visited[i]:
                self.dfs(graph, visited, i)
                components += 1
        
        return components
    
    def intersect(self, a, b):
        return len(set(a) & set(b))
    
    def dfs(self, graph, visited, node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                self.dfs(graph, visited, neighbor)

public class Solution {
    public int NumberOfComponents(int[][] properties, int k) {
        int n = properties.Length;
        List<int>[] graph = new List<int>[n];
        
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        // 构建图
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (Intersect(properties[i], properties[j]) >= k) {
                    graph[i].Add(j);
                    graph[j].Add(i);
                }
            }
        }
        
        // DFS 寻找连通分量
        bool[] visited = new bool[n];
        int components = 0;
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                DFS(graph, visited, i);
                components++;
            }
        }
        
        return components;
    }
    
    private int Intersect(int[] a, int[] b) {
        HashSet<int> setA = new HashSet<int>(a);
        HashSet<int> setB = new HashSet<int>(b);
        setA.IntersectWith(setB);
        return setA.Count;
    }
    
    private void DFS(List<int>[] graph, bool[] visited, int node) {
        visited[node] = true;
        foreach (int neighbor in graph[node]) {
            if (!visited[neighbor]) {
                DFS(graph, visited, neighbor);
            }
        }
    }
}

var numberOfComponents = function(properties, k) {
    const n = properties.length;
    const graph = Array.from({length: n}, () => []);
    
    // 构建图
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (intersect(properties[i], properties[j]) >= k) {
                graph[i].push(j);
                graph[j].push(i);
            }
        }
    }
    
    // DFS 寻找连通分量
    const visited = new Array(n).fill(false);
    let components = 0;
    
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(graph, visited, i);
            components++;
        }
    }
    
    return components;
    
    function intersect(a, b) {
        const setA = new Set(a);
        const setB = new Set(b);
        return new Set([...setA].filter(x => setB.has(x))).size;
    }
    
    function dfs(graph, visited, node) {
        visited[node] = true;
        for (const neighbor of graph[node]) {
            if (!visited[neighbor]) {
                dfs(graph, visited, neighbor);
            }
        }
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n² × m)
空间复杂度O(n² + m)

说明：

  • 时间复杂度：需要检查 O(n²) 对节点，每次计算交集需要 O(m) 时间，DFS 遍历需要 O(n + E) 时间，其中 E 为边数，最多为 O(n²)
  • 空间复杂度：存储图的邻接表最多需要 O(n²) 空间，计算交集时的集合操作需要 O(m) 空间