Leetcode題解 Python & C#：五月挑戰DAY10 Find the Town Judge

有 N 個人(編號 1,...,N)，若所有人信任第x個，而且第x個不信任任何人，若只有一個符合這樣條件的人，回傳其編號。

把條件一一拿來解讀：

他必須被所有人信任，所以那人得到的信任會是 N-1 個。

他不會信任任何人，所以在 trust[i][0] 的人都不是候選人。

於是在遍歷 trust 的同時，要去統計每個編號的被信任數(t[1])，並刪除候選人(t[0])。

剩下的候選人是不相信任何人的人，再剔除其被信任數不為 N-1 的。

最後符合條件1,2，若只剩一個即符合條件3，回傳其編號。若無則-1。

Python

class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        from collections import defaultdict
        beTrust = defaultdict(int)
        candidates = set(range(1,N+1))
        for t in trust:
            beTrust[t[1]] += 1
            if t[0] in candidates: candidates.discard(t[0])
        for c in list(candidates):
            if beTrust[c] != N-1:
                candidates.discard(c)
        if len(candidates) == 1:
            return candidates.pop()
        return -1

C#

public class Solution {
    public int FindJudge(int N, int[][] trust) {        
        var candidates = new HashSet();        
        var beTrusted = new Dictionary();        
        for(int i=1; i <= N; i++)
        {
            candidates.Add(i);
            beTrusted[i]=0;
        }
        foreach(var t in trust){
            beTrusted[t[1]] += 1;
            if(candidates.Contains(t[0]))
            {
                candidates.Remove(t[0]);
            }            
        }
        int result = -1;
        foreach(var c in candidates)
        {
            if(beTrusted[c] == N-1)
            {
                if(result==-1)
                {
                    result = c;
                }
                else
                {
                    return -1;
                }
            }
        }
        return result;
    }
}