資料結構
網路
關係資料庫管理系統 (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 次瀏覽
