拓扑排序题目：喧闹和富有

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题喧闹和富有出处851. 喧闹和富有难度7 级题目描述要求有一组n \texttt{n}n个人从0 \texttt{0}0到n − 1 \texttt{n} - \texttt{1}n−1编号其中每个人都有不同数目的钱以及不同程度的安静值。给定一个数组richer \texttt{richer}richer其中richer[i] [a i , b i ] \texttt{richer[i] [a}_\texttt{i}\texttt{, b}_\texttt{i}\texttt{]}richer[i] [ai​, bi​]表示编号a i \texttt{a}_\texttt{i}ai​比编号b i \texttt{b}_\texttt{i}bi​更有钱。另给定一个整数数组quiet \texttt{quiet}quiet其中quiet[i] \texttt{quiet[i]}quiet[i]是编号i \texttt{i}i的安静值。数组richer \texttt{richer}richer中给出的所有数据逻辑自洽即在编号x \texttt{x}x比编号y \texttt{y}y更有钱的同时不会出现编号y \texttt{y}y比编号x \texttt{x}x更有钱的情况。返回一个整数数组answer \texttt{answer}answer其中answer[x] y \texttt{answer[x] y}answer[x] y的前提是在所有拥有的钱肯定不少于编号x \texttt{x}x的人中编号y \texttt{y}y是最不安静的人即编号y \texttt{y}y对应的quiet[y] \texttt{quiet[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] \texttt{richer [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet [3,2,5,4,6,1,7,0]}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] \texttt{[5,5,2,5,4,5,6,7]}[5,5,2,5,4,5,6,7]解释answer[0] 5 \texttt{answer[0] 5}answer[0] 5。编号5 \texttt{5}5比编号3 \texttt{3}3有更多的钱编号3 \texttt{3}3比编号1 \texttt{1}1有更多的钱编号1 \texttt{1}1比编号0 \texttt{0}0有更多的钱。唯一更为安静有较低的安静值quiet[x] \texttt{quiet[x]}quiet[x]的人是编号7 \texttt{7}7但是目前还不清楚他是否比编号0 \texttt{0}0更有钱。answer[7] 7 \texttt{answer[7] 7}answer[7] 7。在所有拥有的钱肯定不少于编号7 \texttt{7}7的人中这可能包括编号3 \texttt{3}3、4 \texttt{4}4、5 \texttt{5}5、6 \texttt{6}6以及7 \texttt{7}7最安静有较低安静值quiet[x] \texttt{quiet[x]}quiet[x]的人是编号7 \texttt{7}7。其他的答案也可以用类似的推理来解释。示例 2输入richer [], quiet [0] \texttt{richer [], quiet [0]}richer [], quiet [0]输出[0] \texttt{[0]}[0]数据范围n quiet.length \texttt{n} \texttt{quiet.length}nquiet.length1 ≤ n ≤ 500 \texttt{1} \le \texttt{n} \le \texttt{500}1≤n≤5000 ≤ quiet[i] n \texttt{0} \le \texttt{quiet[i]} \texttt{n}0≤quiet[i]nquiet \texttt{quiet}quiet的所有值各不相同0 ≤ richer.length ≤ n × (n − 1) 2 \texttt{0} \le \texttt{richer.length} \le \dfrac{\texttt{n} \times \texttt{(n} - \texttt{1)}}{\texttt{2}}0≤richer.length≤2n×(n−1)​0 ≤ a i , b i n \texttt{0} \le \texttt{a}_\texttt{i}\texttt{, b}_\texttt{i} \texttt{n}0≤ai​, bi​na i ≠ b i \texttt{a}_\texttt{i} \ne \texttt{b}_\texttt{i}ai​bi​richer \texttt{richer}richer中的所有数对各不相同对richer \texttt{richer}richer的观察在逻辑上是一致的解法思路和算法根据每个人的富有程度的相对关系可以将n nn个人构建成有向图每个人是图中的一个顶点每条边表示两个人之间的富有程度的相对关系。如果a aa比b bb更富有则存在一条从a aa指向b bb的有向边。由于给定的数组richer \textit{richer}richer是逻辑自洽的因此不存在环n nn个人构成有向无环图。可以使用拓扑排序得到答案数组中的值。由于题目中的图的表示方式是边数组为了方便处理需要首先将边数组转换成邻接顶点列表的形式转换后可以在O ( 1 ) O(1)O(1)时间获得一个顶点的全部相邻顶点然后使用广度优先搜索实现拓扑排序。拓扑排序时从所有入度为0 00的顶点开始遍历对于每个顶点执行如下操作。得到该顶点的所有后继顶点。对于每个后继顶点将后继顶点的入度减1 11。如果在更新入度之后后继顶点的入度变为0 00则继续对该后继顶点执行搜索。遍历结束之后即可得到拓扑排序的顺序。拓扑排序顺序满足如果图中存在一条从a aa指向b bb的有向边则在拓扑排序顺序中a aa出现在b bb的前面。答案数组的计算可以在拓扑排序的过程中实现。由于每个人拥有的钱肯定不少于其自身因此对于所有0 ≤ i n 0 \le i n0≤in将answer [ i ] \textit{answer}[i]answer[i]初始化为i ii。拓扑排序的过程中当遍历到顶点x xx时所有拥有的钱肯定不少于编号x xx的人都已经遍历过且都已经确定答案数组answer \textit{answer}answer中的对应值answer [ x ] \textit{answer}[x]answer[x]为所有拥有的钱肯定不少于编号x xx的人当中的最不安静的人记z answer [ x ] z \textit{answer}[x]zanswer[x]z zz可能等于x xx。由于quiet \textit{quiet}quiet的所有值各不相同因此对于x xx的后继顶点y yy必有quiet [ y ] ≠ quiet [ z ] \textit{quiet}[y] \ne \textit{quiet}[z]quiet[y]quiet[z]比较quiet [ y ] \textit{quiet}[y]quiet[y]和quiet [ z ] \textit{quiet}[z]quiet[z]可能有以下两种情况。如果quiet [ y ] quiet [ z ] \textit{quiet}[y] \textit{quiet}[z]quiet[y]quiet[z]则所有拥有的钱肯定多于编号y yy的人的安静值都小于y yy的安静值因此answer [ y ] y \textit{answer}[y] yanswer[y]y。如果quiet [ y ] quiet [ z ] \textit{quiet}[y] \textit{quiet}[z]quiet[y]quiet[z]则所有拥有的钱肯定不少于编号y yy的人当中安静值最小的是z zz因此answer [ y ] z \textit{answer}[y] zanswer[y]z。由此可以得到答案数组中的每个元素。代码classSolution{publicint[]loudAndRich(int[][]richer,int[]quiet){intnquiet.length;int[]answernewint[n];for(inti0;in;i){answer[i]i;}int[]indegreesnewint[n];ListInteger[]adjacentArrnewList[n];for(inti0;in;i){adjacentArr[i]newArrayListInteger();}for(int[]edge:richer){indegrees[edge[1]];adjacentArr[edge[0]].add(edge[1]);}QueueIntegerqueuenewArrayDequeInteger();for(inti0;in;i){if(indegrees[i]0){queue.offer(i);}}while(!queue.isEmpty()){intxqueue.poll();ListIntegeradjacentadjacentArr[x];for(inty:adjacent){if(quiet[answer[x]]quiet[answer[y]]){answer[y]answer[x];}indegrees[y]--;if(indegrees[y]0){queue.offer(y);}}}returnanswer;}}复杂度分析时间复杂度O ( n m ) O(n m)O(nm)其中n nn是数组quiet \textit{quiet}quiet的长度m mm是数组richer \textit{richer}richer的长度。将边数组转换成邻接顶点列表的形式需要O ( n m ) O(n m)O(nm)的时间拓扑排序需要O ( n m ) O(n m)O(nm)的时间。空间复杂度O ( n m ) O(n m)O(nm)其中n nn是数组quiet \textit{quiet}quiet的长度m mm是数组richer \textit{richer}richer的长度。邻接顶点列表需要O ( n m ) O(n m)O(nm)的空间队列需要O ( n ) O(n)O(n)的空间因此空间复杂度是O ( n m ) O(n m)O(nm)。