有一组 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.length1 <= n <= 5000 <= quiet[i] < nquiet 的所有值 互不相同0 <= richer.length <= n * (n - 1) / 20 <= ai, bi < nai != biricher 中的所有数对 互不相同- 对
richer 的观察在逻辑上是一致的
Related Topics
👍 204👎 0
DFS，还可以再优化下
- 遍历
int[][] richer数组，生成一个map，构建当前节点和比他小的person节点的关联关系 - 在遍历的过程中，同时知道了哪些节点没有比他大的节点，存放于
HashSet<Integer> starter中 - 从
starter遍历逐个进行DFS，利用int[] quiet数组中对应的喧嚣值往下深搜的时候代入更新到结果int[] ans数组中 - 由于在初始化的时候赋值了
Arrays.fill(ans,501)每个值为501，所以如果当前喧嚣值比当前的ans[i]大或者等于的话就不用继续往下更新了 - 最终
int[] ans数组中存的是当前对应的quiet值，又因为quiet 的所有值 互不相同所以根据反向映射关系重新赋值更新为对应的person - 其实
int[] ans中也可以一开始就存对应的person,不用最终再转换一遍，但是一开始用quiet来比较运算比较直观点，所以就先这么写了 - 最终结果返映射的时候，如果当前
ans[i]依然等于501，说明这个点是独立的，不和其他点有相关联，那么对应依旧为quiet[i] int[] ans数组也可以一开始就等于int[] quiet数组，但是这样的话再dfs过程中判断大小的时候需要再借助其他手段判断是否需要再往下层更新
代码
class Solution {
// richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]],
// quiet = [3,2,5,4,6,1,7,0]
// 6 5
// ↓ ↙
// 2 3 ← 4
// ↓ ↙ ↘
// 1 7
// ↓
// 0
HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
int[] ans;
int[] quiet;
int[] quietToPerson;
public int[] loudAndRich(int[][] richer, int[] quiet) {
this.quiet = quiet;
ans = new int[quiet.length];
Arrays.fill(ans,501);
quietToPerson = new int[quiet.length];
for (int i = 0; i < quiet.length; i++) {
quietToPerson[quiet[i]] = i;
}
HashSet<Integer> starter = new HashSet<>();
for (int[] ints : richer) {
if (!map.containsKey(ints[0])){
map.put(ints[0],new HashSet<>());
}
map.get(ints[0]).add(ints[1]);
starter.remove(ints[1]);
starter.add(ints[0]);
}
starter.forEach(i -> {
dfs(i,quiet[i]);
});
for (int i = 0; i < ans.length; i++) {
ans[i]= quietToPerson[ans[i]>500?quiet[i]:ans[i]];
}
return ans;
}
public void dfs(int num, int min){
if (min > quiet[num]){
min = quiet[num];
}
if (ans[num] > min){
ans[num] = min;
}else{
return;
}
if (map.containsKey(num)){
int finalMin = min;
map.get(num).forEach(integer -> {
dfs(integer, finalMin);
});
}
}
}
发表评论