AlgoPressAppearance
0997-找到小镇的法官
https://leetcode.cn/problems/find-the-town-judge
小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。
如果小镇法官真的存在，那么：
- 小镇法官不会信任任何人。
- 每个人（除了小镇法官）都信任这位小镇法官。
- 只有一个人同时满足属性 1 和属性 2 。
给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。
如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。
示例 1：
输入：n = 2, trust = [[1,2]] 输出：2 示例 2：
输入：n = 3, trust = [[1,3],[2,3]] 输出：3 示例 3：
输入：n = 3, trust = [[1,3],[2,3],[3,1]] 输出：-1
提示：
- 1 <= n <= 1000
- 0 <= trust.length <= 104
- trust[i].length == 2
- trust 中的所有trust[i] = [ai, bi] 互不相同
- ai != bi
- 1 <= ai, bi <= n
思路
每个人都信任法官，所以我们找出法官的编号，加入hash表。 题目并没有说他信任了法官，就不可以信任别人 找出最多别人信任的人，他就是应该就是法官。 此时需要查看法官没有信任别人
参考代码
csharp
public class Solution {
public int FindJudge(int n, int[][] trust) {
if(trust.Length == 0 && n == 1){
return n;
}
Dictionary<int,int> dict = new Dictionary<int,int>();
Dictionary<int,int> dict2 = new Dictionary<int,int>(); //信任别人的人
int judge = -1;
int max = 0;
for(int i=0; i< trust.Length; i++){
int people = trust[i][0];
if(!dict2.ContainsKey(people)){
dict2.Add(people,people);
}
int val = trust[i][1];
if(!dict.ContainsKey(val)){
dict.Add(val,1);
}
else{
dict[val]++;
}
if(dict[val] > max){
judge = val;
max = dict[val];
}
}
if(!dict2.ContainsKey(judge) && n == max+1){
return judge;
}
else{
return -1;
}
}
}
思路2：入度和出度
在有向图中，一个节点的入度是指向该节点的边的数量，一个节点的出度是指从该节点发出的边的数量。 题目描述了一个有向图。 每个人是图的节点， trust 元素 trust[i] 是图的有向边，从 trust[i][0] 指向 trust[i][1] 遍历 trust 统计入度和出度。
根据题意，在法官存在的情况下，法官不相信任何人，每个人（除了法官外）都信任法官，且只有一名法官。因此法官这个节点的入度是 n-1, 出度是 0 我们可以遍历每个节点的入度和出度，如果找到一个符合条件的节点，由于题目保证只有一个法官，我们可以直接返回结果；如果不存在符合条件的点，则返回 -1
参考测试案例：应该返回 -1 而非 3
3
[[1,3],[2,3],[3,1]]
参考代码
csharp
public class Solution {
public int FindJudge(int n, int[][] trust) {
int[] ingress = new int[n+1];
int[] egress = new int[n+1];
for(int i=0; i<trust.Length; i++){
ingress[trust[i][1]]++;
egress[trust[i][0]]++;
}
for(int i=1; i<=n; i++){
//注意：如果入度是 n-1， 此时还需要判断该节点的出度为 0
if(ingress[i] == n-1 && egress[i] == 0){
return i;
}
}
return -1;
}
}
复习:20220703
csharp
public class Solution {
public int FindJudge(int n, int[][] trust) {
//统计入度，法官的入度应该是 n-1，如果没找到，则说明没有法官
//注意还需要统计出度，如果法官入度是n-1,他的出度也必须为0
//注意遍历的时候，需要遍历人数，而不是遍历 ingress 数组，否则会漏掉 1,[] ingress为空的这种情况
int[] ingress = new int[n+1];
int[] egress = new int[n+1];
for(int i=0; i<trust.Length; i++){
ingress[trust[i][1]]++;
egress[trust[i][0]]++;
}
for(int i=1; i<=n; i++){
if(ingress[i] == n-1 && egress[i] == 0){
return i;
}
}
return -1;
}
}