【LeetCode】851.喧闹与富有（思路+题解）

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 更有钱。
answer7 = 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 的观察在逻辑上是一致的

LeetCode源地址：

https://leetcode-cn.com/problems/loud-and-rich/

二、思路

1.题目理解

数组richer是一个这样的数组：其位置1的兄弟总比0位置的兄弟更加富有，但其安静值并不见得比0位置的安静值更低，而n个人的安静值，都存储在数组quiet中；而我们需要返回的数组answer的组成是：answer[i]的值为，在比第i位兄弟更富有的人群中，最安静的那位的标号i。

2.解题思路

使用哈希表提高搜索速度。
创建一个哈希表mp，其内容组成是：对于数组richer进行遍历，对于每个richer出现过的相对穷人作为key，其对应的value值为在已遍历的richer[0:i,:]中比该穷人更富有的人中最安静的那位的标号i。

举个例子：
对于richer = [[0,1],[1,2]], quiet = [0,1,2]来说，0是比1更富有的存在，1是比2更富有的存在，那么当遍历到数组第一行时，由于0的安静值为(quiet[0] = 0)<(quiet[1] = 1)，加入mp的一对键值对应为pair<int,int>(1,0)，而遍历在第二行时可知1是比2更富有的存在，但此时应当在mp中对key为1的键值对进行搜索，查看是否存在比1更加富有且安静的大佬，并对比此时彼此的安静值，并总是保留最安静的一位，此时第二对键值对就应为pair<int,int>(0,2),重复下去，完成mp的构建

在完成哈希表mp的构建后，进行答案answer的填写与输出。由前面有关结果的分析可知，我们要在answer[i]中保存比第i位兄弟富有的人中最安静的大佬。但由于mp中只是保留了对每个key兄弟来讲最安静且富有的大佬value，而其本身可能存在比其自己更穷的人i，也有可能在richer中并没有体现存在肯定比i富有的人，因此mp中也许会不存在i的信息。
故mp中若没有i的信息，则说明不存在一定比i富有且安静的人，那么此时i自己本身就是那个不穷于自己且安静的答案。
若能找到i的信息，则继续爬出最安静的大佬

时间与空间复杂度分析：
时间复杂度：O(n),n是数组richer的长度，哈希表的查找时间为O(1),vector的下标访问时间也为O(1)
空间复杂度：O(n),最坏的情况将每个兄弟的信息都保留，长度为n

成绩：

三、代码

class Solution {
public:vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {if (quiet.size() == 1)		//处理特殊return { 0 };unordered_map<int, int>mp;for (int i = 0; i < richer.size(); ++i) {if (mp.count(richer[i][1]) == 0)		//若mp无该位穷兄弟信息mp.insert(pair<int, int>(richer[i][2], richer[i][0]));else			//若mp有该位穷兄弟信息，则对比新旧quiet信息，更新更安静的quiet[mp.at(richer[i][3])] > quiet[richer[i][0]]?mp[richer[i][4]] = richer[i][0] : mp[richer[i][5]];int temp = richer[i][0];			//开始顺延而上爬出比richer[i][6]穷兄弟富有的人里面最安静的，保证value为最安静的那位int quietest = temp;while (mp.count(temp) != 0) {temp = mp.at(temp);if (quiet[temp] < quiet[quietest])quietest = temp;}quiet[mp.at(richer[i][7])] > quiet[quietest] ? mp[richer[i][8]] = quietest : mp[richer[i][9]];}		//完成构建mp，mp中的value都是比其key富有的人中，最安静的vector<int>res;for (int i = 0; i < quiet.size(); ++i) {		//开始更新结果if (mp.count(i) == 0)		//若mp中没有该兄弟的信息，则自己就是结果（没有人确定比本人富有，则自己就是那个不穷于自己的安静者）res.push_back(i);else {			//若mp中有信息，则爬出最安静的那位int temp = mp.at(i);int quietest = temp;while (mp.count(temp) != 0) {temp = mp.at(temp);if (quiet[temp] < quiet[quietest])quietest = temp;}quiet[i] > quiet[quietest] ? res.push_back(quietest) : res.push_back(i);}}return res;}
};