leetcode 997. Find the Town Judge [Easy]

題目敘述

小鎮中有 N 個人，其中有一個是 Judge，需要同時滿足：

• Judge 本身不信任任何人
• 其他 N-1 個人都信任 Judge

一開始往圖的方向思考，但寫出來的解法不太理想。後來換個思路：用一個大小為 N 的 array 記錄每個人的「淨信任分數」，若 A 信任 B 就 array[B]++, array[A]--。如果 Judge 存在，它的分數就是 N-1（被所有人信任但自己不信任任何人）。

解題紀錄

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> record(n+1, 0);
        
        for (int i = 0; i < trust.size(); ++i) {
            record[trust[i][0]]--;
            record[trust[i][1]]++;
        }
        
        for (int i = 1; i <= n; ++i) {
            if (record[i] == n-1) {
                return i;
            }
        }
        return -1;
    }
};