C++ 中每个人成为朋友的最早时刻
假设在一个社交群中，有 N 个不同的人，他们有从 0 到 N-1 的唯一整数 id。这里我们有一个日志列表，其中每个 logs[i] = [time, id_A, id_B] 包含一个非负整数时间戳，以及两个不同人的 id。每个日志都显示两个不同的人成为朋友的时间。如果 A 是 B 的朋友，那么 B 也是 A 的朋友。假设如果 A 是 B 的朋友，那么 A 就认识 B，或者 A 是某个认识 B 的人的朋友。我们必须找出每个人认识其他每个人的最早时间。如果没有找到这样的时间，则返回 -1 所以如果输入如下:[[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。这是因为第一个事件发生在时间戳 = 20190101，在人 0 和 1 成为朋友后，我们就有了友谊组 [0,1], [2], [3], [4], [5]。然后第二个事件发生在时间戳 = 20190104，在人 3 和人 4 成为朋友后，我们有以下友谊组 [0,1], [2], [3,4], [5]。 之后第三个事件发生在时间戳 = 20190107，在人 2 和人 3 成为朋友后，我们有以下友谊组 [0,1], [2,3,4], [5]。 然后第四个事件发生在时间戳 = 20190211，在人 1 和人 5 成为朋友后，我们有以下友谊组 [0,1,5], [2,3,4]。 之后第五个事件发生在时间戳 = 20190224，由于人 2 和人 4 已经是朋友，所以任何事情都会发生。最后，第六个事件发生在时间戳 = 20190301，在人 0 和 3 成为朋友后，我们所有人都成为了朋友。
为了解决这个问题，我们将遵循以下步骤 −
定义一个名为 find() 的方法，它将接受一个值 x，它将按如下方式工作 −
如果 parents[x] 为 -1，则返回 x
parents[x] := find(parents[x])
返回 parents[x]
在主方法中，它将按如下方式工作 −
定义两个名为 parents 和 rank 的数组，大小为 N，用 -1 填充 parents，用 1 填充 rank
对logs
对 logs 中的每个元素 i −
对 i[1] 和 i[2] 执行并集
find(i[2]) 和 find(i[1])
如果 N 在等级数组中，则返回 i[0]
返回 -1
Example(C++)
让我们看下面的实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int earliestAcq(vector<vector<int>>& logs, int N) {
vector<int> ds (N, -1);
sort(begin(logs), end(logs));
for(vector<int> &k : logs) {
if(un(k[1], k[2], ds) == N) return k[0];
}
return -1;
}
int un(int u, int v, vector<int> & ds) {
u = find(u, ds);
v = find(v, ds);
if(u != v) {
ds[v] += ds[u];
ds[u] = v;
}
return -ds[v];
}
int find(int u, vector<int> & ds) {
return ds[u] < 0? u : ds[u] = find(ds[u], ds);
}
};
main(){
vector<vector<int>> v = {
{20190101,0,1},{20190104,3,4},{20190107,2,3},{20190211,1,5},
{20190224,2,4},{20190301,0,3},{20190312,1,2},{20190322,4,5}
};
Solution ob;
cout <<ob.earliestAcq(v, 6);
}
输入
[[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5], [20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]] 6
输出
20190301
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
