Medium

题目描述

有一组 n 个人，标记为 0 到 n - 1，每个人都有不同的金钱数量和不同的安静程度。

给你一个数组 richer，其中 richer[i] = [ai, bi] 表示 ai 比 bi 更富有，以及一个整数数组 quiet，其中 quiet[i] 是第 i 个人的安静程度。richer 中给定的所有数据在逻辑上都是正确的（即，数据不会导致 x 比 y 富有且 y 比 x 富有的情况同时出现）。

返回一个整数数组 answer，其中 answer[x] = y，如果 y 是在所有确定比人 x 有相等或更多金钱的人中最安静的人（即具有最小 quiet[y] 值的人 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.
人 5 比人 3 富有，人 3 比人 1 富有，人 1 比人 0 富有。
唯一更安静的人（具有更低 quiet[x]）是人 7，但不清楚他们是否比人 0 更富有。
answer[7] = 7.
在所有确定比人 7 有相等或更多金钱的人（可能是人 3, 4, 5, 6, 或 7）中，最安静的人（具有更低 quiet[x]）是人 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. 首先构建一个有向图，如果 a 比 b 富有，则从 b 指向 a，表示从 b 可以到达比他更富有的人 a
  2. 对于每个人 x，我们需要找到所有可以从 x 出发能到达的人（包括 x 自己），然后在这些人中找到最安静的
  3. 使用DFS遍历图，对于每个节点，递归地找到其所有"富有邻居"中最安静的人

算法步骤：

  1. 根据 richer 数组构建邻接表图
  2. 使用DFS + 记忆化搜索，对于每个人计算答案
  3. 在DFS过程中，对于当前节点，比较自己和所有富有邻居的安静程度，选择最安静的

优化： 使用记忆化避免重复计算，因为可能存在多条路径到达同一个富有的人。

代码实现

class Solution {
public:
    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
        int n = quiet.size();
        vector<vector<int>> graph(n);
        
        // 构建图：如果a比b富有，则b->a
        for (auto& r : richer) {
            graph[r[1]].push_back(r[0]);
        }
        
        vector<int> answer(n, -1);
        
        function<int(int)> dfs = [&](int x) -> int {
            if (answer[x] != -1) return answer[x];
            
            answer[x] = x;  // 初始化为自己
            
            // 检查所有比x富有的人
            for (int y : graph[x]) {
                int candidate = dfs(y);
                if (quiet[candidate] < quiet[answer[x]]) {
                    answer[x] = candidate;
                }
            }
            
            return answer[x];
        };
        
        for (int i = 0; i < n; i++) {
            dfs(i);
        }
        
        return answer;
    }
};

class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        n = len(quiet)
        graph = [[] for _ in range(n)]
        
        # 构建图：如果a比b富有，则b->a
        for a, b in richer:
            graph[b].append(a)
        
        answer = [-1] * n
        
        def dfs(x):
            if answer[x] != -1:
                return answer[x]
            
            answer[x] = x  # 初始化为自己
            
            # 检查所有比x富有的人
            for y in graph[x]:
                candidate = dfs(y)
                if quiet[candidate] < quiet[answer[x]]:
                    answer[x] = candidate
            
            return answer[x]
        
        for i in range(n):
            dfs(i)
        
        return answer

public class Solution {
    public int[] LoudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.Length;
        List<int>[] graph = new List<int>[n];
        
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        // 构建图：如果a比b富有，则b->a
        foreach (var r in richer) {
            graph[r[1]].Add(r[0]);
        }
        
        int[] answer = new int[n];
        Array.Fill(answer, -1);
        
        int Dfs(int x) {
            if (answer[x] != -1) return answer[x];
            
            answer[x] = x;  // 初始化为自己
            
            // 检查所有比x富有的人
            foreach (int y in graph[x]) {
                int candidate = Dfs(y);
                if (quiet[candidate] < quiet[answer[x]]) {
                    answer[x] = candidate;
                }
            }
            
            return answer[x];
        }
        
        for (int i = 0; i < n; i++) {
            Dfs(i);
        }
        
        return answer;
    }
}

var loudAndRich = function(richer, quiet) {
    const n = quiet.length;
    const graph = Array.from({length: n}, () => []);
    
    // 构建图：如果a比b富有，则b->a
    for (const [a, b] of richer) {
        graph[b].push(a);
    }
    
    const answer = new Array(n).fill(-1);
    
    const dfs = (x) => {
        if (answer[x] !== -1) return answer[x];
        
        answer[x] = x;  // 初始化为自己
        
        // 检查所有比x富有的人
        for (const y of graph[x]) {
            const candidate = dfs(y);
            if (quiet[candidate] < quiet[answer[x]]) {
                answer[x] = candidate;
            }
        }
        
        return answer[x];
    };
    
    for (let i = 0; i < n; i++) {
        dfs(i);
    }
    
    return answer;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n + m)，其中 n 是人数，m 是 richer 数组的长度。每个节点和每条边都只访问一次
空间复杂度O(n + m)，用于存储图的邻接表和递归调用栈

相关题目