喧闹和富有

难度: Medium

有一组 n 个人作为实验对象，从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值（quietness）。为了方便起见，我们将编号为 x 的人简称为 "person x "。

给你一个数组 richer ，其中 richer[i] = [a_i, b_i] 表示 person a_i 比 person b_i 更有钱。另给你一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值。richer 中所给出的数据 逻辑自洽（也就是说，在 person x 比 person y 更有钱的同时，不会出现 person y 比 person x 更有钱的情况）。

现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是，在所有拥有的钱肯定不少于 person x 的人中，person y 是最不安静的人（也就是安静值 quiet[y] 最小的人）。

示例 1：

输入：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 3，4，5，6 以及 7），
最安静（有较低安静值 quiet[x]）的人是 person 7。
其他的答案也可以用类似的推理来解释。

示例 2：

输入：richer = [], quiet = [0]
输出：[0]

提示：

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

Submission

运行时间: 38 ms

内存: 22.7 MB

class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        n=len(quiet)
        g=[[]for _ in range(n)]
        for x,y in richer:
            g[y].append(x)
        ans=[-1]*n
        def dfs(x):
            if ans[x]!=-1:
                return
            ans[x]=x
            for y in g[x]:
                dfs(y)
                if quiet[ans[y]]<quiet[ans[x]]:
                    ans[x]=ans[y]
        for i in range(n):
            dfs(i)
        return ans

Explain

这道题目可以使用深度优先搜索（DFS）来解决。首先，我们根据richer数组构建一个图g，其中g[y]包含所有比person y更有钱的人。然后，我们初始化一个答案数组ans，其中ans[x]表示在所有拥有的钱不少于person x的人中，最不安静的人的编号。我们对每个人i进行深度优先搜索，搜索过程中，如果我们访问到一个人x，我们首先检查ans[x]是否已经被计算过，如果没有，我们将ans[x]初始化为x自身，然后对于x的每一个财富大于他的人y，我们递归地调用dfs(y)，并更新ans[x]为quiet值最小的人。最终，ans数组就是我们的答案。

时间复杂度: O(r + n)

空间复杂度: O(n)

class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        n = len(quiet)
        g = [[] for _ in range(n)]
        for x, y in richer:
            g[y].append(x)
        ans = [-1] * n

        def dfs(x):
            if ans[x] != -1:
                return
            ans[x] = x
            for y in g[x]:
                dfs(y)
                if quiet[ans[y]] < quiet[ans[x]]:
                    ans[x] = ans[y]

        for i in range(n):
            dfs(i)
        return ans

Explore

在题解中，图g的构建基于richer数组，其中每个元素[x, y]表示x比y更富有。在这种情况下，我们构建的是一个有向图，其中方向代表'更富有'这一关系。由于'更富有'是严格的单向关系（A比B富有不意味着B也比A富有），因此理论上不应存在环。也就是说，'更富有'关系应该构成了一个拓扑排序。然而，为了在实现中保证安全且环不存在，我们可以在执行DFS之前，使用拓扑排序检测算法如Kahn算法或通过DFS检测环的存在，确保这一点。

在实现DFS和更新ans数组时，如果多个人拥有相同的最小安静值，题解中的算法默认保留在ans[x]中首先找到的那个人的编号。由于DFS的性质和图的构建方式，通常这意味着节点ID较小的人将被优先考虑。这是由于在构建图g时加入节点的顺序以及递归调用的顺序决定的。

是的，在构建图g时，确实考虑了列表可能为空的情况。对于那些没有比他们更有钱的人的个体，他们在图g中对应的列表将为空。在DFS执行过程中，当遇到这样的个体时，由于他们没有更有钱的人，DFS将不会进一步递归调用，而是直接将该人的编号作为答案保留在ans中，因为他们自己就是在其可达群体中最不安静的人。

实际代码中使用了一个简单的检查来避免对同一节点重复计算。在DFS函数的开始，会检查ans[x]是否已经不是初始化值（在这种情况下是-1）。如果ans[x]不是-1，这意味着我们之前已经计算过x的值，因此可以直接返回而不需要再次计算。这个机制确保了每个节点只被计算一次，从而防止了不必要的重复工作和潜在的无限循环。