Zombie Cluster

作者 QIFAN 日期 2016-09-27
Zombie Cluster

题干

僵尸病毒在村子里猖獗,正常人类会被僵尸传染。传染有传递性,比如 A 僵尸传染了 B 僵尸, B 僵尸传染了 C 僵尸,则认为 {A, B, C} 为一个僵尸部落(cluster)。村庄里有 n 个僵尸,给出此村庄的僵尸关系图。若 a[i][j]=1 ,则代表 A 传染了 B ,根据该关系图找出村庄内的僵尸部落个数。

给定一个 String 数组,标记了 N 个僵尸相互之间的关系。返回 unique cluster 的个数。

举例
输入: [11000,11000,00100,00011,00011]

输出: 3

解释:
根据输入可知关系图如下。

| | a | b | c | d | e |
|---|---|---|---|---|---|
| a | 1 | 1 | | | |
| b | 1 | 1 | | | |
| c | | | 1 | | |
| d | | | | 1 | 1 |
| e | | | | 1 | 1 |
|---|---|---|---|---|---|

僵尸各自都知道自己是僵尸,所以 (i, i) 坐标值都为 1 ,另外 (a,b)=1 , 即 a 传染了 b (a-->b),同理 b-->ad-->ee-->d 。 所以一共有三个集合,分别为 {a,b}, {c}, {d,e}

思路

Union Find

可使用Union Find算法。将同一个 cluster 的僵尸 id 标记一样。最后的 unique id 个数就是 cluster 数目。

时间复杂度:$O(N^2)$ 需要遍历整个数组。空间复杂度:$O(N^2)$ 。

代码:

public int zombieCluster(String[] zombies) {
if (zombies == null || zombies.length < 2) return 0;
// 新建一个僵尸数组
int[] clusters = new int[zombies.length];
// 标记初始值
for (int i = 0; i < cluster.length; i++) {
clusters[i] = i;
}
for (int i = 0; i < zombies.length; i++) {
for(int j = 0; j < zombies[i].length(); j++) {
if(zombies[i].charAt(j) == '1') {
union(clusters, i, j);
}
}
}
//排序一下方便数
Arrays.sort(cluster);
int count = 0;
int current = cluster[0];
for (int i = 1; i < cluster.length; i++) {
if (current != cluster[i]) {
count++;
current = cluster[i];
}
}
// 别忘了比较最后一个
if (current != cluster[cluster.length-2]) count++;
return count;
}
void union(int[] a, int i, int j) {
a[j] = a[j];
}

Note: 有其他更简洁的方法还请赐教!

DFS

2017.01.17 更新
多谢评论 @Han Wen ,下面是 DFS 解法。时间复杂度同样是 $O(N^2) $ ,空间复杂度为 $O(N^2)$ 。相比于 union find ,虽然空间复杂度多了一倍,但少了后面排序的时间,感觉差不多吧。

public int zombieCluster(String[] zombies) {
int N = Integer.parseInt(zombies.length);
int[][] M = new int [N][N];
for (int i = 0; i < N; i++) {
for (int j = 0 ; j < N; j++) {
M[i][j] = Integer.parseInt(zombies[i].charAt(j) + "");
}
}
// 已访问过的
boolean visited[] = new boolean[N];
// 正在访问
boolean visiting[] = new boolean[N];
int count = 0;
for (int i = 0; i < N; ++i) {
if (!visited[i]) {
visiting[i] = true;
DFS(M, N, visited, visiting, i);
visited[i] = true;
count++;
}
}
return count;
}
private void DFS(int M[][], int N, boolean visited[], boolean[] visiting, int s)
{
if (!visited[s] ) {
visiting[s] = true;
for (int j = s + 1; j < N; j++) {
if (M[s][j] == 1 && !visited[j]) {
visiting[j] = true;
DFS(M, N, visited, visiting, j);
visited[j] = true;
}
}
}
}

reference :
https://gist.github.com/abhijitdhar/7005a0c03d1a882f7ac9741495f76ccb