在一個(gè)小鎮(zhèn)里，按從 1 到 N 標(biāo)記了 N 個(gè)人。傳言稱，這些人中有一個(gè)是小鎮(zhèn)上的秘密法官。

如果小鎮(zhèn)的法官真的存在，那么：

小鎮(zhèn)的法官不相信任何人。

1. 每個(gè)人（除了小鎮(zhèn)法官外）都信任小鎮(zhèn)的法官。
2. 只有一個(gè)人同時(shí)滿足屬性 1 和屬性 2 。
3. 給定數(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

思路:

• 又是一個(gè)簡單的映射數(shù)組問題
• 維護(hù)兩個(gè)列表:
  1. 每個(gè)人被信任的人數(shù)
  2. 每個(gè)人是否信任別人
• 最終進(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表示每個(gè)人被信任的次數(shù), trustResult表示每個(gè)人被信任的次數(shù). 采用N+1的數(shù)組大小, 這樣下標(biāo)即是人員編號(hào)
• 若這個(gè)人不信任別人, 且信任他的人是N-1(除了自己以外的所有人), 則返回這個(gè)人的編號(hào)

總結(jié):

• 木了