Leetcode 547.省份数量(中等)
LeetCode 数量 中等 省份
2023-09-11 14:15:38 时间
题目
题解
可以把
n
个城市和它们之间的相连关系看成图,城市是图中的节点,相连关系是图中的边,给定的矩阵isConnected
即为图的邻接矩阵,省份即为图中的连通分量。
计算省份总数,等价于计算图中的连通分量数,可以通过深度优先搜索或广度优先搜索实现,也可以通过并查集实现。
解法一:深度优先搜索
【思路】
遍历所有城市,对于每个城市,如果该城市尚未被访问过,则从该城市开始深度优先搜索,通过矩阵
sConnected
得到与该城市直接相连的城市有哪些,这些城市和该城市属于同一个连通分量,然后对这些城市继续深度优先搜索,直到同一个连通分量的所有城市都被访问到,即可得到一个省份。遍历完全部城市以后,即可得到连通分量的总数,即省份的总数。
【代码】
class Solution {
public:
//DFS
void dfs(vector<vector<int>> &isConnected, vector<int> &visited, int provinces, int i) {
for (int j = 0; j < provinces; j++) {
if (isConnected[i][j] == 1 && !visited[j]) {
visited[j] = 1;
dfs(isConnected, visited, provinces, j);
}
}
}
int findCircleNum(vector<vector<int>>& isConnected) {
int provinces = isConnected.size();
vector<int> visited(provinces);
int ans = 0;
for (int i = 0; i < provinces; i++) {
if (!visited[i]) {
ans++;
dfs(isConnected, visited, provinces, i);
}
}
return ans;
}
};
【复杂度分析】
- 时间复杂度: O ( n 2 ) O(n^2) O(n2),其中 n n n 是城市的数量。需要遍历矩阵 n n n 中的每个元素。
- 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是城市的数量。需要使用数组 v i s i t e d visited visited 记录每个城市是否被访问过,数组长度是 n n n,递归调用栈的深度不会超过 n n n。
解法二:广度优先搜索
【思路】
也可以通过广度优先搜索的方法得到省份的总数。对于每个城市,如果该城市尚未被访问过,则从该城市开始广度优先搜索,直到同一个连通分量中的所有城市都被访问到,即可得到一个省份。
【代码】
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int provinces = isConnected.size();
vector<int> visited(provinces);
queue<int> que;
int ans = 0;
for (int i = 0; i < provinces; i++) {
if (!visited[i]) {
que.push(i);
while (!que.empty()) {
int j = que.front();
que.pop();
visited[j] = 1;
for (int k = 0; k < provinces; k++) {
if (isConnected[j][k] == 1 && !visited[k]) {
que.push(k);
}
}
}
ans++;
}
}
return ans;
}
};
【复杂度分析】
- 时间复杂度:
O
(
n
2
)
O(n^2)
O(n2),其中
n
n
n 是城市的数量。需要遍历矩阵
isConnected
中的每个元素。 - 空间复杂度:
O
(
n
)
O(n)
O(n),其中
n
n
n 是城市的数量。需要使用数组
visited
记录每个城市是否被访问过,数组长度是 n n n,广度优先搜索使用的队列的元素个数不会超过 n n n。
解法三:并查集
【思路】
计算连通分量数的另一个方法是使用并查集。初始时,每个城市都属于不同的连通分量。遍历矩阵
isConnected
,如果两个城市之间有相连关系,则它们属于同一个连通分量,对它们进行合并。
遍历矩阵isConnected
的全部元素之后,计算连通分量的总数,即为省份的总数。
【代码】
class Solution {
private:
void init(int n) {
parent.resize(n);
for (int i = 0; i < n; i++)
parent[i] = i;
}
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
void merge(int p, int q) {
int pp = find(p), pq = find(q);
if (pp != pq) parent[pp] = pq;
}
vector<int> parent;
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
if (n == 0) return 0;
int ans = n;
init(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (isConnected[i][j] == 1) {
if (find(i) != find(j)) {
ans--;
parent[find(i)] = find(j);
}
}
}
}
return ans;
}
};
【复杂度分析】
- 时间复杂度:
O
(
n
2
log
n
)
O(n^2 \log n)
O(n2logn),其中
n
n
n 是城市的数量。需要遍历矩阵
isConnected
中的所有元素的一半,时间复杂度是 O ( n 2 ) O(n^2) O(n2),如果遇到相连关系,则需要进行 2 次查找和最多 1 次合并,一共需要进行 2 n 2 2n^2 2n2次查找和最多 n 2 n^2 n2次合并,因此总时间复杂度是 O ( 2 n 2 log n 2 ) = O ( n 2 log n ) O(2n^2 \log n^2)=O(n^2 \log n) O(2n2logn2)=O(n2logn)。这里的并查集使用了路径压缩,但是没有使用按秩合并,最坏情况下的时间复杂度是 O ( n 2 log n ) O(n^2 \log n) O(n2logn),平均情况下的时间复杂度依然是 O ( n 2 α ( n ) ) O(n^2 \alpha (n)) O(n2α(n)),其中 α \alpha α 为阿克曼函数的反函数, α ( n ) \alpha (n) α(n) 可以认为是一个很小的常数。 - 空间复杂度:
O
(
n
)
O(n)
O(n),其中
n
n
n 是城市的数量。需要使用数组
parent
记录每个城市所属的连通分量的祖先。
相关文章
- Java实现 LeetCode 726 原子的数量(递归+HashMap处理)
- Java实现 LeetCode 713 乘积小于K的子数组(子集数量+双指针)
- Java实现 LeetCode 678 有效的括号字符串(暴力+思路转换)
- Java实现 LeetCode 670 最大交换(暴力)
- Java实现 LeetCode 567 字符串的排列(滑动窗口,处理区间内的字符数量)
- Java实现 LeetCode 567 字符串的排列(滑动窗口,处理区间内的字符数量)
- Java实现 LeetCode 470 用 Rand7() 实现 Rand10()
- Java实现 LeetCode 470 用 Rand7() 实现 Rand10()
- Java实现 LeetCode 452 用最少数量的箭引爆气球
- Java实现 LeetCode 202 快乐数
- Java实现 LeetCode 14 最长公共前缀
- Java实现LeetCode #986 - Interval List Intersections
- LeetCode-1742. 盒子中小球的最大数量【哈希表,暴力】
- LeetCode - 200 岛屿数量
- Leetcode 1128. 等价多米诺骨牌对的数量(终于解决)
- Leetcode 1128. 等价多米诺骨牌对的数量(终于解决)
- [LeetCode] 448. 找到所有数组中消失的数字 ☆