這是悅樂書的第373次更新，第400篇原創(chuàng)
01 看題和準(zhǔn)備
今天介紹的是LeetCode算法題中Easy級別的第234題（順位題號是997）兵睛。在一個城鎮(zhèn)醒陆，有N個人從1到N標(biāo)記伊履。有傳言說其中一個人是秘密的鎮(zhèn)法官。
如果鎮(zhèn)法官存在葫录，那么：
鎮(zhèn)法官不信任任何人挺邀。
每個人（鎮(zhèn)法官除外）都信任鎮(zhèn)法官蝠嘉。
只有一個人滿足前兩條缴允。
給定一個trust數(shù)組，一對trust[i] = [a珍德，b]表示被標(biāo)記為a的人信任標(biāo)記為b的人练般。
如果鎮(zhèn)法官存在并且可以識別，則返回鎮(zhèn)法官的標(biāo)簽锈候。否則薄料，返回-1。
例如：
輸入：N = 2泵琳，trust = [[1,2]]
輸出：2
輸入：N = 3摄职，trust = [[1,3]，[2,3]]
輸出：3
輸入：N = 3获列，trust = [[1,3]谷市，[2,3]，[3,1]]
輸出：-1
輸入：N = 3击孩，trust = [[1,2]迫悠，[2,3]]
輸出：-1
輸入：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
02 第一種解法
將題目翻譯一下就是忌警，法官的被信任次數(shù)等于N-1搁拙，并且法官不能信任其他人，即法官是trust數(shù)組中trust[i][1]出現(xiàn)次數(shù)等于N-1的人（被信任次數(shù)等于N-1），并且trust[i][0]不等于法官所在的標(biāo)簽（法官不能信任其他人）感混。
思路：利用HashMap記錄被信任人出現(xiàn)的次數(shù)端幼，找出其中被信任了N-1次的人，然后去trust數(shù)組中判斷此人是否有信任過其他人弧满。有種特殊情況是N為1的時候婆跑，trust為空數(shù)組，即只有1個人庭呜，那么這個人就是法官滑进。
public int findJudge(int N, int[][] trust) {
// 只有1個人的時候，法官就是他本人
if (N == 1) {
return N;
}
// key為被信任的人募谎，value為其被信任的次數(shù)
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int[] arr : trust) {
map.put(arr[1], map.getOrDefault(arr[1], 0)+1);
}
// 找到被信任次數(shù)等于N-1的那個人
int count = -1;
for (Integer key : map.keySet()) {
if (map.get(key) == N-1) {
count = key;
}
}
// 被信任次數(shù)等于N-1的人扶关，不能信任其他人
for (int[] arr : trust) {
if (arr[0] == count) {
return -1;
}
}
return count;
}
03 第二種解法
針對第一種解法中的HashMap，我們還可以用int數(shù)組進(jìn)行替換数冬，思路和上面第一種解法一致节槐。
public int findJudge2(int N, int[][] trust) {
if (N == 1) {
return N;
}
int[] trusted = new int[N+1];
for (int i=0; i<trust.length; i++) {
trusted[trust[i][1]]++;
}
int count = -1;
for (int i=0; i<trusted.length; i++) {
if (trusted[i] == N-1) {
count = i;
}
}
for (int[] arr : trust) {
if (arr[0] == count) {
return -1;
}
}
return count;
}
04 第三種解法
針對第二種解法，我們還可以將其簡化成2個for循環(huán)拐纱，將統(tǒng)計被信任次數(shù)和尋找被信任次數(shù)最多的人合在一起處理铜异。
public int findJudge3(int N, int[][] trust) {
if (N == 1) {
return N;
}
int[] trusted = new int[N+1];
int count = -1, num = -1;
for (int i=0; i<trust.length; i++) {
trusted[trust[i][1]]++;
if (trusted[trust[i][1]] > count) {
count = trusted[trust[i][1]];
num = trust[i][1];
}
}
// 被信任次數(shù)要等于N-1
if (count != N-1) {
return -1;
}
for (int[] arr : trust) {
if (arr[0] == num) {
return -1;
}
}
return num;
}
05 第四種解法
我們還可以使用兩個int數(shù)組來解，一個數(shù)組arr存信任的人秸架，另一個數(shù)組arr2存被信任的人揍庄，找出被信任次數(shù)等于N-1（arr2[i]=N-1）且沒有信任過人（arr[i]=0）的人，他就是法官东抹。
public int findJudge4(int N, int[][] trust) {
int[] arr = new int[N+1];
int[] arr2 = new int[N+1];
for (int i=0; i<trust.length; i++) {
arr[trust[i][0]]++;
arr2[trust[i][1]]++;
}
for (int j=1; j<arr.length; j++) {
if (arr[j] == 0 && arr2[j] == N-1) {
return j;
}
}
return -1;
}
06 小結(jié)
算法專題目前已連續(xù)日更超過七個月蚂子，算法題文章240+篇，公眾號對話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】缭黔、【算法】食茎、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集馏谨。
以上就是全部內(nèi)容董瞻，如果大家有什么好的解法思路、建議或者其他問題田巴，可以下方留言交流钠糊，點贊、留言壹哺、轉(zhuǎn)發(fā)就是對我最大的回報和支持抄伍！
