题目

在一个小镇里，按从 1 到 N 标记了 N 个人。传言称，这些人中有一个是小镇上的秘密法官。

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

小镇的法官不相信任何人。
每个人（除了小镇法官外）都信任小镇的法官。
只有一个人同时满足属性 1 和属性 2 。

给定数组 trust，该数组由信任对 trust[i] = [a, b] 组成，表示标记为 a 的人信任标记为 b 的人。

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

示例 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

提示：

1 <= N <= 1000
trust.length <= 10000
trust[i] 是完全不同的
trust[i][0] != trust[i][1]
1 <= trust[i][0], trust[i][1] <= N

In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

The town judge trusts nobody.
Everybody (except for the town judge) trusts the town judge.
There is exactly one person that satisfies properties 1 and 2.

You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled atrusts the person labelled b.

If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1.

Example 1:

1 2	Input: N = 2, trust = [[1,2]] Output: 2

Example 2:

1 2	Input: N = 3, trust = [[1,3],[2,3]] Output: 3

Example 3:

1 2	Input: N = 3, trust = [[1,3],[2,3],[3,1]] Output: -1

Example 4:

1 2	Input: N = 3, trust = [[1,2],[2,3]] Output: -1

Example 5:

1 2	Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]] Output: 3

Note:

1 <= N <= 1000
trust.length <= 10000
trust[i] are all different
trust[i][0] != trust[i][1]
1 <= trust[i][0], trust[i][1] <= N

解题方法

法官被N-1个村民信任（入度为N-1），法官不信任任何人（出度为0）。遍历一次trust，用一个二维数组记录每个村民的信任出入度，出度为0，入度为N-1的为法官。这段代码跑了5ms，超过了99.24%的Java提交。

class Solution {
    // Method 1 5ms 99.24%
    public int findJudge(int N, int[][] trust) {
        int[][] people = new int[N][2];	// store the indegree and outdegree of each person
        for(int[] trus : trust) {
            people[trus[0]-1][0]++;
            people[trus[1]-1][1]++;
        }
        for(int i = 0; i < N; i++) {
            if(people[i][0] == 0 && people[i][1] == N - 1) {	// indegree == 0 & outdegree == N-1
                return i + 1;
            }
        }
        return -1;
    }
}

节省空间开支，除了法官村民们都有信任的人，出度>0，入度-出度<N-1，只需要一个一维数组来保存每个村民的入度与出度差，只有法官的入度-出度=N-1。

class Solution {
    // Method 1 5ms 99.24%
  	public int findJudge(int N, int[][] trust) {
        int[] people = new int[N];
        for(int[] person : trust) {
            // judge doesn't trust anyone
            people[person[0]-1]--;
            // people all except judge trust judge
            people[person[1]-1]++;
        }
        for(int i = 0; i < N; i++) {
            if(people[i] == N - 1) {
                return i + 1;
            }
        }
        return -1;
    }
}