→ DJYOSHITAKA: 大師...02/24 18:54
推 sustainer123: 大師02/24 18:55
推 oin1104: 大師 教我 02/24 18:56
教三小，去開你的銀趴
推 wu10200512: 大師02/24 18:57
※ 編輯: JIWP (42.73.133.158 臺灣), 02/24/2024 18:58:33
→ NCKUEECS: 大師 02/24 18:58
推 Che31128: 大師 02/24 19:01
你版今天線蟲帥朝都去FF惹
剩我還在解每日leetcode，今天還是hard，我要吐了
2092. Find All People With Secret
有0~n-1個人，並且0有一個秘密，他告訴了firstPerson
有一個array meetings[x,y,time]
如果x、y其中一個人知道了秘密他就會告訴對方
而且一個人在同時間可以有多個meetings，假設他在time=i的時候知道了秘密
那麼在time=i跟他meeting的人都會知道秘密
請問最後會有多少人知道秘密
思路 :
直覺這是一題graph搭配union-find
建立find function來找該節點的group
將meeting按照時間排序
接著建立1個groups array，並且設值group[i]=i
將index 0、firstPerson設成0
去依照meeting時間遍歷meetings矩陣
每一次分別找meetings[i][0]、meetings[i][1]屬於哪個group
並且把較大的那個group的值更改成較小的group
要進到下個meeting時間的時候重置group矩陣
如果find(group,i)=0 那就將group[i]=0
不然group[i]=i
這個時間內有meetings的人才要重置，所以有一個array去紀錄該時間有誰meeting過
如果不紀錄，而是0~n全部重置會超出時間限制
最後去找group[i]=0的就是答案
golang code
func find(array *[]int, index int) int {
for (*array)[index] != index {
index = (*array)[index]
}
return index
}
func findAllPeople(n int, meetings [][]int, firstPerson int) []int {
slices.SortFunc[[][]int, []int](meetings, func(i, j []int) int {
return i[2] - j[2]
})
group := make([]int, n)
for i := 0; i < n; i++ {
group[i] = i
}
group[firstPerson] = 0
i := 0
l := len(meetings)
temp := []int{}
for i < l {
time := meetings[i][2]
temp = temp[:0]
for i < l && meetings[i][2] == time {
g1 := find(&group, meetings[i][0])
g2 := find(&group, meetings[i][1])
group[max(g1, g2)] = min(g1, g2)
temp = append(temp, meetings[i][0], meetings[i][1])
i++
}
for _, val := range temp {
if find(&group, val) != 0 {
group[val] = val
} else {
group[val] = 0
}
}
}
ans := []int{}
for i:=0;i<n;i++{
if group[i]==0{
ans = append(ans, i)
}
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.133.158 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1708771697.A.7AA.html