题目
在一个社交圈子当中,有 n
个人。每个人都有一个从 0
到 n - 1
的唯一编号。我们有一份日志列表 logs
,其中 logs[i] = [timestampi, xi, yi]
表示 xi
和 yi
将在同一时间 timestampi
成为朋友。
友谊是 相互 的。也就是说,如果 a
和 b
是朋友,那么 b
和 a
也是朋友。同样,如果 a
和 b
是朋友,或者 a
是 b
朋友的朋友 ,那么 a
和 b
是熟识友。
返回圈子里所有人之间都熟识的最早时间。如果找不到最早时间,就返回 -1
。
示例 1:
输入:logs = [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]], N = 6
输出:20190301
解释:
第一次结交发生在 timestamp = 20190101,0 和 1 成为好友,社交朋友圈如下 [0,1], [2], [3], [4], [5]。
第二次结交发生在 timestamp = 20190104,3 和 4 成为好友,社交朋友圈如下 [0,1], [2], [3,4], [5].
第三次结交发生在 timestamp = 20190107,2 和 3 成为好友,社交朋友圈如下 [0,1], [2,3,4], [5].
第四次结交发生在 timestamp = 20190211,1 和 5 成为好友,社交朋友圈如下 [0,1,5], [2,3,4].
第五次结交发生在 timestamp = 20190224,2 和 4 已经是好友了。
第六次结交发生在 timestamp = 20190301,0 和 3 成为好友,大家都互相熟识了。
示例 2:
输入: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
输出: 3
提示:
2 <= n <= 100
1 <= logs.length <= 10^4
logs[i].length == 3
0 <= timestampi <= 10^9
0 <= xi, yi <= n - 1
xi != yi
timestampi
中的所有时间戳 均不同- 所有的对
(xi, yi)
在输入中最多出现一次
解题
方法一:并查集
思路
彼此熟悉的关系看作边,人看作顶点构建出一个无向图,把日志列表按照时间升序排序,维护一个并查集(ds
)然后遍历日志数组:
- 合并当前遍历到的日志中的两个顶点。
- 如果当前图的连通分量为
1
说明所有人都互相熟识了,返回当前的时间戳。
如果遍历完成后图的连通分量还没减为 1
则说明图中有人互相还不认识,还没一整个的社交圈子,也就找不到时间戳,返回 -1
。
代码
class Solution {
public int earliestAcq(int[][] logs, int n) {
Arrays.sort(logs, (a, b) -> a[0] - b[0]);
DisjointSet ds = new DisjointSet(n);
for (int[] log : logs) {
if (!ds.isConnected(log[1], log[2])) {
ds.union(log[1], log[2]);
if (ds.groups == 1) return log[0];
}
}
return -1;
}
}
class DisjointSet {
public int groups;
private int[] setArr;
public DisjointSet(int n) {
groups = n;
setArr = new int[groups];
for (int i = 0; i < groups; i++) setArr[i] = i;
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP != rootQ) {
setArr[rootP] = rootQ;
groups--;
}
}
public int find(int n) {
return n == setArr[n] ? n : (setArr[n] = find(setArr[n]));
}
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
}
评论区