0851. 喧闹和富有

0851. 喧闹和富有 #

  • 标签:深度优先搜索、图、拓扑排序、数组
  • 难度:中等

题目大意 #

描述:有一组 n 个人作为实验对象,从 0n - 1 编号,其中每个人都有不同数目的钱,以及不同程度的安静值 quietness

现在给定一个数组 richer,其中 richer[i] = [ai, bi] 表示第 ai 个人比第 bi 个人更有钱。另给你一个整数数组 quiet,其中 quiet[i] 是第 i 个人的安静值。数组 richer 中所给出的数据逻辑自洽(也就是说,在第 ai 个人比第 bi 个人更有钱的同时,不会出现第 bi 个人比第 ai 个人更有钱的情况 )。

要求:返回一个长度为 n 的整数数组 answer 作为答案,其中 answer[i] 表示在所有比第 i 个人更有钱或者和他一样有钱的人中,安静值最小的那个人的编号。

说明

  • $n == quiet.length$
  • $1 \le n \le 500$。
  • $0 \le quiet[i] \le n$。
  • $quiet$ 的所有值互不相同。
  • $0 \le richer.length \le n * (n - 1) / 2$。
  • $0 \le ai, bi < n$。
  • $ai != bi$。
  • $richer$ 中的所有数对 互不相同。
  • 对 $richer$ 的观察在逻辑上是一致的。

示例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
输入    richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
输出    [5,5,2,5,4,5,6,7]

解释
answer[0] = 5
person 5 比 person 3 有更多的钱person 3 比 person 1 有更多的钱person 1 比 person 0 有更多的钱
唯一较为安静有较低的安静值 quiet[x]的人是 person 7
但是目前还不清楚他是否比 person 0 更有钱
answer[7] = 7
在所有拥有的钱肯定不少于 person 7 的人中这可能包括 person 3456 以及 7),
最安静有较低安静值 quiet[x]的人是 person 7
其他的答案也可以用类似的推理来解释

解题思路 #

思路 1:拓扑排序 #

对于第 i 个人,我们要求解的是比第 i 个人更有钱或者和他一样有钱的人中,安静值最小的那个人的编号。

我们可以建立一张有向无环图,由富人指向穷人。这样,对于任意一点来说(比如 x),通过有向边链接的点(比如 y),拥有的钱都没有 x 多。则我们可以根据 answer[x] 去更新所有 x 能连接到的点的 answer 值。

我们可以先将数组 answer 元素初始化为当前元素编号。然后对建立的有向无环图进行拓扑排序,按照拓扑排序的顺序去更新 x 能连接到的点的 answer 值。

思路 1:拓扑排序代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import collections

class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        
        size = len(quiet)
        indegrees = [0 for _ in range(size)]
        edges = collections.defaultdict(list)

        for x, y in richer:
            edges[x].append(y)
            indegrees[y] += 1

        res = [i for i in range(size)]
        queue = collections.deque([])
        for i in range(size):
            if not indegrees[i]:
                queue.append(i)

        while queue:
            x = queue.popleft()
            size -= 1
            for y in edges[x]:
                if quiet[res[x]] < quiet[res[y]]:
                    res[y] = res[x]
                indegrees[y] -= 1
                if not indegrees[y]:
                    queue.append(y)
        return res
本站总访问量  次  |  您是本站第  位访问者