在一个小镇里，按从 1 到 n 为 n 个人进行编号。传言称，这些人中有一个是小镇上的秘密法官。
如果小镇的法官真的存在，那么：
小镇的法官不相信任何人。
每个人（除了小镇法官外）都信任小镇的法官。
只有一个人同时满足条件 1 和条件 2 。
给定数组 trust，该数组由信任对 trust[i] = [a, b] 组成，表示编号为 a 的人信任编号为 b 的人。
如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的编号。否则，返回 -1。
示例 1：输入：n = 2, trust = [[1,2]] 输出：2
示例 2：输入：n = 3, trust = [[1,3],[2,3],[3,1]] 输出：-1
解题思路：可以构造一个关于各节点的hash表，这个hash表是二维的，hash[i][0]表示i-1节点的入度，hash[i][1]表示i-1节点的出度。由题可知，法官节点的入度为n-1，出度为0。
public int findJudge(int n, int[][] trust) {
int[][] hashTable = new int[n][2]; // 构造hash表
for(int[] tmp : trust) {
hashTable[tmp[1]-1][0]++; // tmp[1]-1节点的入度加1
hashTable[tmp[0]-1][1]++; // tmp[0]-1节点的出度加1
}
for(int i=0; i<n; i++) {
if(hashTable[i][0]==n-1 && hashTable[i][1]==0) { // 如果i节点的入度为n-1，出度为0
return i+1; // 则返回法官编号i+1
}
}
return -1; //否则返回-1
}
网友评论