Сложность: medium
В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi.
Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b.
Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1.
Пример:
Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output: 3
Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.
👨💻 Алгоритм:
1⃣Отсортируйте логи по времени в хронологическом порядке, так как в задаче не указано, отсортированы ли они.
2⃣Пройдитесь по отсортированным логам, применяя структуру данных "Объединение-Поиск":
Для каждого лога объедините двух участников, упомянутых в логе, с помощью функции union(a, b).
Каждое объединение добавляет новые связи между участниками.
3⃣Следите за количеством групп:
Изначально каждый участник рассматривается как отдельная группа.
Количество групп уменьшается с каждым полезным объединением.
Момент, когда количество групп уменьшается до одной, является самым ранним моментом, когда все участники становятся связанными (друзьями). Верните этот момент времени.
Если такого момента не существует, верните -1.
😎 Решение:
class UnionFind {
private var parent: [Int]
private var rank: [Int]
init(_ n: Int) {
parent = Array(0..<n)
rank = Array(repeating: 1, count: n)
}
func find(_ x: Int) -> Int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
func union(_ x: Int, _ y: Int) -> Bool {
let rootX = find(x)
let rootY = find(y)
if rootX != rootY {
if rank[rootX] > rank[rootY] {
parent[rootY] = rootX
} else if rank[rootX] < rank[rootY] {
parent[rootX] = rootY
} else {
parent[rootY] = rootX
rank[rootX] += 1
}
return true
}
return false
}
}
class Solution {
func earliestAcq(_ logs: [[Int]], _ n: Int) -> Int {
let sortedLogs = logs.sorted { $0[0] < $1[0] }
var groupCount = n
let uf = UnionFind(n)
for log in sortedLogs {
let timestamp = log[0]
let friendA = log[1]
let friendB = log[2]
if uf.union(friendA, friendB) {
groupCount -= 1
}
if groupCount == 1 {
return timestamp
}
}
return -1
}
}Ставь 👍 и забирай 📚 Базу знаний