0851. Loud and Rich¶
题目信息¶
- 题号:
0851
- 难度:
Medium
- 主题:
有向关系、传递可达、安静程度
- 原题:
- 重点:
richer 关系具有传递意义;对每个人从所有财富不少于他的人中选择 quiet 值最小者,候选包括本人
题目重述¶
有 n 个人,编号为 0 至 n - 1。数组 richer 中的关系 [a, b] 表示人物 a 比人物 b 更富有;所有关系互不重复并且逻辑一致,不会形成互相都更富有的矛盾。数组 quiet[i] 表示人物 i 的安静程度,数值越小越安静,并且所有值互不相同。
对于每个人 x,考虑所有能够确定财富不少于 x 的人:包括 x 本人、直接比 x 富有的人,以及通过关系传递可知更富有的人。请返回数组 answer,其中 answer[x] 是这些候选中 quiet 值最小者的编号。
n == quiet.length,1 <= n <= 500;quiet 是 0 至 n - 1 的一个排列;0 <= richer.length <= n * (n - 1) / 2,每对关系端点合法且不同,所有关系互不重复并保证逻辑一致。
自建示例¶
财富关系沿链传递:
输入:richer = [[1,0],[2,1]], quiet = [2,1,0]
输出:[2,2,2]
解释:人物 2 比人物 1 富有,人物 1 又比人物 0 富有,因此人物 2 的财富不少于三个人中的任何一个,并且 quiet[2] 最小。
没有任何财富比较关系:
输入:richer = [], quiet = [1,0]
输出:[0,1]
解释:richer 长度达到允许的最小值 0。无法确定任何一个人比另一个人更富有,因此每个人的候选集合只有本人,答案分别是 0 和 1。