彼此熟识的最早时间

1101. 彼此熟识的最早时间

在一个社交圈子当中，有 n 个人。每个人都有一个从 0 到 n - 1 的唯一编号。我们有一份日志列表 logs，其中 logs[i] = [timestamp_i, x_i, y_i] 表示 x_i 和 y_i 将在同一时间 timestamp_i成为朋友。

友谊是相互的。也就是说，如果 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⁴
logs[i].length == 3
0 <= timestamp_i <= 10⁹
0 <= x_i, y_i <= n - 1
x_i != y_i
timestamp_i 中的所有时间戳均不同
所有的对 (xi, yi) 在输入中最多出现一次

相似题目

省份数量

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int earliestAcq(vector<vector<int>>& logs, int n) { } };

golang 解法, 执行用时: 12 ms, 内存消耗: 4.8 MB, 提交时间: 2023-10-21 20:10:21

func earliestAcq(logs [][]int, n int) int {
    // 按时间排序
    sort.Slice(logs, func(i,j int) bool {
        return logs[i][0]<logs[j][0]
    })
    // 并查集
    var root = make([]uint8, n)
    for i := range root{
        root[i] = uint8(i)
    }
    // 查找
    var find = func(i uint8) uint8{
        for i!=root[i]{
            i = root[i]
        }
        return i
    }
    // 好友数量，初始为1：自己
    var cnt = 1
    // 合并，如果产生新的好友，则好友数量+1
    var union = func(a,b uint8){
        x,y := find(a), find(b)
        if x!=y{
            cnt++
        }
        root[uint8(x)] = uint8(y)
    }
    for _, item := range logs{
        union(uint8(item[1]), uint8(item[2]))
        // 好友数据为n时所有人都熟识了
        if cnt==n{
            return item[0]
        }
    }
    return -1
}

cpp 解法, 执行用时: 28 ms, 内存消耗: 13.1 MB, 提交时间: 2023-10-21 20:09:57

class Solution {
public:
    int earliestAcq(vector<vector<int>>& logs, int N) {
        vector<int> par(N);
        for(int i = 0; i < N; i++)
            par[i] = i;
        int count = N;
        sort(logs.begin(), logs.end());
        for(auto iter : logs){
            int p1 = iter[1];
            int p2 = iter[2];
            while(par[p1] != p1)
                p1 = par[p1];
            while(par[p2] != p2)
                p2 = par[p2];
            if(p1 == p2)
                continue;
            else{
                par[p1] = p2;
                if(--count == 1)
                    return iter[0];
            }
        }
        return -1;
    }
};

java 解法, 执行用时: 6 ms, 内存消耗: 42.6 MB, 提交时间: 2023-10-21 20:09:34

class Solution {

    private int[] parents; // 并查集的数据结构
    private int count; // 当前集合的数量

    public int earliestAcq(int[][] logs, int N) {
        // initialise (英式拼法)
        count = N;
        parents = new int[N];
        for (int i = 0; i < N; ++i) parents[i] = i;

        List<LogInfo> infos = new ArrayList<>();
        for (int[] l : logs)
            infos.add(new LogInfo(l[0], l[1], l[2]));
        infos.sort((a, b) -> a.timestamp - b.timestamp);

        for (LogInfo l: infos) {
            union(l.id_a, l.id_b);
            if (count == 1) return l.timestamp;
        }

        return -1;
    }

    private int find(final int x) {
        if (parents[x] == x) return x;
        parents[x] = find(parents[x]);
        return parents[x];
    }

    private void union(final int a, final int b) {
        
        if (a == b) return;

        final int pa = find(a);
        final int pb = find(b);
        if (pa == pb) return;

        parents[pb] = pa;
        --count;
    }

    private static class LogInfo {
        int timestamp;
        int id_a;
        int id_b;

        LogInfo(int timestamp, int id_a, int id_b) {
            this.timestamp = timestamp;
            this.id_a = id_a;
            this.id_b = id_b;
        }
    }
}

python3 解法, 执行用时: 52 ms, 内存消耗: 16.4 MB, 提交时间: 2023-10-21 20:09:07

class Solution:
    def earliestAcq(self, logs: List[List[int]], N: int) -> int:
        p=[i for i in range(N)]
        logs.sort(key=lambda x: x[0])

        def find(x, p):
            if x!=p[x]: return find(p[x], p)
            else: return p[x]
        
        for l in logs:
            p1, p2=find(l[1], p), find(l[2], p)
            if p1==p2: continue
            p[p1]=p2
            N-=1
            if N==1: return l[0]

        return -1

上一题

下一题

详情