数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中所有人成为朋友的最早时刻
假设在一个社交群体中，有N个不同的人，其唯一的整数ID从0到N-1。这里我们有一份日志列表，其中每个logs[i] = [时间，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
对日志进行排序
对于日志中的每个元素i：
对i[1]和i[2]执行合并操作
查找find(i[2])和find(i[1])
如果rank数组中存在N，则返回i[0]
返回-1
示例 (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
94 次浏览
