在一個小鎮(zhèn)里怠苔，按從 1 到 N 標(biāo)記了 N 個人同廉。傳言稱，這些人中有一個是小鎮(zhèn)上的秘密法官。
如果小鎮(zhèn)的法官真的存在迫肖，那么：
小鎮(zhèn)的法官不相信任何人锅劝。
- 每個人（除了小鎮(zhèn)法官外）都信任小鎮(zhèn)的法官。
- 只有一個人同時滿足屬性 1 和屬性 2 蟆湖。
- 給定數(shù)組 trust故爵，該數(shù)組由信任對 trust[i] = [a, b] 組成，表示標(biāo)記為 a 的人信任標(biāo)記為 b 的人隅津。
如果小鎮(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
思路:
- 又是一個簡單的映射數(shù)組問題
- 維護(hù)兩個列表:
- 每個人被信任的人數(shù)
- 每個人是否信任別人
- 最終進(jìn)行統(tǒng)計(jì)即可
代碼:
public int findJudge(int N, int[][] trust) {
if (N == 1) {
return 1;
}
int[] trustNum = new int[N + 1];
boolean[] trustResult = new boolean[N + 1];
Arrays.fill(trustResult, false);
for (int i = 0; i < trust.length; i++) {
trustNum[trust[i][1]]++;
trustResult[trust[i][0]] = true;
}
for (int i = 0; i < N + 1; i++) {
if (trustResult[i] || trustNum[i] < N - 1) {
continue;
}
return i;
}
return -1;
}
分析:
-
trustNum表示每個人被信任的次數(shù),trustResult表示每個人被信任的次數(shù). 采用N+1的數(shù)組大小, 這樣下標(biāo)即是人員編號 - 若這個人不信任別人, 且信任他的人是N-1(除了自己以外的所有人), 則返回這個人的編號
總結(jié):
- 木了
