友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
851. 喧闹和富有
有一组 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] 最小的人）。
示例 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 <= ai, bi < n -
ai != bi -
richer中的所有数对 互不相同 -
对
richer的观察在逻辑上是一致的
思路分析
这不就是深度优先搜索吗？先构件图，再按图索骥。
| 看题解，说拓扑排序也可以。想想也对，有机会试试。 |
-
一刷
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
30
31
32
33
34
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-08-06 22:47:30
*/
public int[] loudAndRich(int[][] richer, int[] quiet) {
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] r : richer) {
int a = r[0];
int b = r[1];
graph.computeIfAbsent(b, _ -> new ArrayList<>()).add(a);
}
int n = quiet.length;
int[] result = new int[n];
Arrays.fill(result, -1);
for (int i = 0; i < n; i++) {
dfs(graph, quiet, result, i);
}
return result;
}
// 未优化 通过 71 / 86 个测试用例 -> 23.68%
private void dfs(Map<Integer, List<Integer>> graph,
int[] quiet, int[] result, int i) {
if (result[i] != -1) {
return;
}
result[i] = i;
for (Integer n : graph.getOrDefault(i, Collections.emptyList())) {
dfs(graph, quiet, result, n);
if (quiet[result[n]] < quiet[result[i]]) {
result[i] = result[n];
}
}
}