997. 找到小镇的法官（24.9.22）

题目

小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称这些人中有一个暗地里是小镇法官。如果小镇法官真的存在，那么：

1. 小镇法官不会信任任何人。
2. 每个人（除了小镇法官）都信任这位小镇法官。
3. 只有一个人同时满足属性 1 和属性 2。

给出一个数组 trust，其中 trust[i]=[a_i,b_i] 表示编号为 a_i 的人信任编号为 b_i 的人。如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -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. $1\le n\le 1000$。
2. $0\le trust.length\le 10^4$。
3. trust[i].length == 2，且 trust 中的所有 trust[i]=[a_i,b_i] 互不相同。
4. $1\le a_i,b_i\le n$，且 $a_i\ne b_i$。

解题思路

根据题目意思得出法官拥有两种特点，一是不信任任何人，二是被所有人信任，那么我们假设一共有n人，那么法官对应的信任的人为0，被n-1个人信任，那么我们只需要统计各自的信任的人数和被信任的人数。

代码

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> to_trust(n+1);//信任他人
        vector<int> from_trust(n+1);//来自他人的新人
        for(vector<int> num:trust){
            from_trust[num[1]]++;
            to_trust[num[0]]++;
        }
        for(int i=1;i<=n;i++){
            if(from_trust[i]==n-1&&to_trust[i]==0)
            return i;
        }
        return -1;
    }
};

原文地址：https://blog.csdn.net/qq_60624992/article/details/142441182

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！