找到小镇的法官

力扣 997. 找到小镇的法官

题目说明

在一个小镇里，按从 1 到 n 为 n 个人进行编号。传言称，这些人中有一个是小镇上的秘密法官。

如果小镇的法官真的存在，那么：

小镇的法官不相信任何人。
每个人（除了小镇法官外）都信任小镇的法官。
只有一个人同时满足条件 1 和条件 2 。
给定数组 trust，该数组由信任对 trust[i] = [a, b] 组成，表示编号为 a 的人信任编号为 b 的人。

如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的编号。否则，返回 -1。

提示：

1 <= numBottles <= 100
2 <= numExchange <= 100

示例

示例 1:

1 2	输入：n = 2, trust = [[1,2]] 输出：2

示例 2:

1 2	输入：n = 3, trust = [[1,3],[2,3]] 输出：3

示例 3:

1 2	输入：n = 3, trust = [[1,3],[2,3],[3,1]] 输出：-1

示例 4:

1 2	输入：n = 3, trust = [[1,2],[2,3]] 输出：-1

示例 5:

1 2	输入：n = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]] 输出：3

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，发现此题不会出现某个人信任自己的情况，所以我们统计每个人信任和被信任的情况即可，让我们来看看具体如何实现的吧。

实现

class Solution {
    /**
     * 数组
     */
    public int findJudge(int n, int[][] trust) {
        int result = -1;
        
        // 相信过几个人
        int[] tru = new int [n + 1];
        // 被几个人相信
        int[] beTru = new int [n + 1];
        
        
        for (int[] temp: trust) {
            tru[temp[0]]++;
            beTru[temp[1]]++;
        }
        
        for(int i = 1; i <= n; i++) {
            // 当此人被其他所有人信任且不信任别人
            // 即可假定其是秘密法官
            if (beTru[i] == n - 1 && tru[i] == 0) {
                if (result == -1) {
                    result = i;
                }
                // 多于一人时说明无法确定
                else {
                    return -1;
                }
            }
        }
        
        return result;
    }
}