851.Loud and Rich

发表于 | 分类于

题目详见：https://leetcode.com/problems/loud-and-rich/

思路：广度搜索。

首先初始化answer[i]=i，即为其本身，然后建立一个二维graph，graph[i]存储的是遍历richer得到的比i有钱的人。并在遍历richer的时候给answer[i]赋值为当前遍历得到的符合要求的最小quiet的j。接下来从0开始，依次循环遍历graph，每次循环先将graph[i]中的元素压入临时队列que,然后进行广度搜索，在搜索的同时进行quiet的比较。由于之前在遍历richer的时候已经得到并存储了每组的quiet最小值，所以此时的比较是当前组的quiet值与出队元素组的quiet值的比较，就不用一个一个地比。当graph[0]搜索完成后，得到的answer[0]就是最后的结果，当后续graph[i]进行搜索时，若出队元素为0时，则无需将graph[0]中的元素压入队列，只需与answer[0]比较即可。runtime:48ms,由于queue不支持遍历，set虽然可以去重，但效率比vector低很多，所以graph使用$vector>$。

+
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
35
36
class Solution {
public:
    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
        int N=quiet.size();
        vector<int> answer;
        for(int i=0;i<N;i++){
            answer.push_back(i);
        }
        vector<vector<int>> graph(N);
        for(auto item:richer){
            graph[item[1]].push_back(item[0]);    
            if(quiet[answer[item[1]]]>quiet[item[0]])
                answer[item[1]]=item[0];
        }
        for(int i=0;i<N;i++){                        
            if(graph[i].size()>0){
                queue<int> que_i;
                for(auto x:graph[i]){
                    que_i.push(x);
                }                
                while(que_i.size()>0){
                    int index=que_i.front();
                    que_i.pop();
                    if(graph[index].size()>0){    
                        if(quiet[answer[i]]>quiet[answer[index]])
                                answer[i]=answer[index];
                        if(index>i)                            
                            for(auto x:graph[index])
                                que_i.push(x);                        
                    }                
                }                
            }
        }
        return answer;
    }
};