題目： LeetCode - 997. Find the Town Judge

題目說明

給一個整數及一個陣列，整數代表某個城鎮的居民總數，陣列代表某個城鎮居民的信任關係，例如 [1, 2] 就代表居民 1 信任居民 2。題目要求我們找到城鎮中的法官，而法官會有以下特點：

  • 法官被其他所有人所信任
  • 法官不相信任何人

※ 陣列中不會有重複的信任關係，例如居民 1 信任居民 2，則 [1, 2] 就會出現在陣列中並且只會出現一次。

解題思路

使用一個陣列來紀錄居民們的信任關係，trusts[i][0] 代表居民 i 相信幾個人，trusts[i][1] 代表居民 i 被幾個人所信任。而法官必須滿足以下條件：

  • trusts[i][0] == 0：因為法官不能相信任何人。
  • trusts[i][1] == N - 1：因為法官必須被除了自己以外的所有人所信任。

若是居民 i 滿足以上的條件，則居民 i 就是法官。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    int findJudge(int N, vector<vector<int>>& trust) {
        auto trusts = vector<vector<int>>(N + 1, vector<int>(2));
        for(auto i : trust)
            ++trusts[i[0]][0], ++trusts[i[1]][1];
        for(int i = 1; i <= N; ++i)
            if(!trusts[i][0] && trusts[i][1] == N - 1)
                return i;
        return -1;
    }
};