有一组 n 个人作为实验对象,从 0 到 n - 1 编号,其中每个人都有不同数目的钱,
以及不同程度的安静值(quietness)
为了方便起见,我们将编号为 x 的人简称为 "person x "。
给你一个数组 richer ,其中 richer[i] = [ai, bi] 表示 person ai 比 person bi 更有钱
另给你一个整数数组 quiet ,其中 quiet[i] 是 person i 的安静值
richer 中所给出的数据 逻辑自洽
也就是说,在 person x 比 person y 更有钱的同时,不会出现 person y 比 person x 更有钱的情况
现在,返回一个整数数组 answer 作为答案,其中 answer[x] = y 的前提是:
在所有拥有的钱肯定不少于 person x 的人中,person y 是最安静的人(也就是安静值 quiet[y] 最小的人)。
拓扑排序。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
richer := [][]int{{1, 0}, {2, 1}, {3, 1}, {3, 7}, {4, 3}, {5, 3}, {6, 3}}
quiet := []int{3, 2, 5, 4, 6, 1, 7, 0}
ret := loudAndRich(richer, quiet)
fmt.Println(ret)
}
// richer[i] = {a, b} a比b更有钱 a -> b
// quiet[i] = k, i这个人安静值是k
func loudAndRich(richer [][]int, quiet []int) []int {
N := len(quiet)
// a -> b
// a -> c
// b -> c
// a : b c
// b : c
// nexts[0] = {5,7,3}
// 0 : 5 7 3
// 5最没钱的,
// nexts[5] = { }
nexts := make([][]int, 0)
for i := 0; i < N; i++ {
// 0 : {}
// 1 : {}
// n-1 : {}
nexts = append(nexts, make([]int, 0))
}
// 入度
// 0 : 0
// 1 : 2
degree := make([]int, N)
for _, r := range richer {
// [a,b] a -> b
nexts[r[0]] = append(nexts[r[0]], r[1])
degree[r[1]]++
}
// 所有入度为0的点,入队列
zeroQueue := make([]int, N)
l := 0
r := 0
for i := 0; i < N; i++ {
if degree[i] == 0 {
zeroQueue[r] = i
r++
}
}
// ans[i] = j : 比i有钱的所有人里,j最安静
ans := make([]int, N)
for i := 0; i < N; i++ {
ans[i] = i
}
for l < r { // 如果队列不空
// 弹出一个入度为0的点
cur := zeroQueue[l]
l++
// 1) 消除当前cur的影响!
for _, next := range nexts[cur] {
// cur : 比cur有钱,最安静的!ans[cur]
if quiet[ans[next]] > quiet[ans[cur]] {
ans[next] = ans[cur]
}
degree[next]--
if degree[next] == 0 {
zeroQueue[r] = next
r++
}
}
}
return ans
}
执行结果如下: