997. Find the Town Judge

町にN人住んでおり、彼らは1からNの数字でラベリングされている。この中に一人だけ裁判官がいるという噂があるので、それを特定する。

裁判官が存在する場合の条件は以下のとおり。

裁判官は誰も信じない
(裁判官を除く)全員が裁判官を信じる
この1.と2.を満たす人が1人だけいる

trustという配列が与えられ、trust[i] = [a, b]はaはbを信じるということを意味する。上記条件が満たされる場合はそのラベルを返し、それ以外の場合は-1を返す。

Example 5:

Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]

Output: 3

My Answer

以下のようなコードになり、2回目の提出でAC(Accepted)が出た。時間計算量は $O(n+t)$ 、空間計算量は $O(n)$ となる。

class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        ppl = set()
        score = [0 for i in range(N)]
        for i in range(len(trust)):
            ppl.add(trust[i][0])
            ind = trust[i][1]
            score[ind-1] += 1 
        if len(ppl) == N:
            return -1
        maxNum = max(score)
        if score.count(maxNum) == 1:
            return score.index(maxNum) + 1
        return -1

実行速度は780 msとなり、全体の85.63 %の参加者より速い結果となった。単純な英語力不足から、問題の意味を正しく理解するのに時間がかかってしまった。最終的に、問題を翻訳していて上記コードはたまたまACしているだけと気付いた。

Best Answer

この問題の解答はプレミアム会員でないと閲覧することができなかった。こういう時は大抵問題についてのディスカッションフォーラムを参照するかYouTubeにある解説動画を探すようにしている。

www.youtube.com

動画内の説明はJavaで記述されていたので、Pythonで書き直した。

class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        count = [0] * (N+1)
        for t in trust:
            count[t[0]] -= 1
            count[t[1]] += 1
        for i in range(1, N+1):
            if count[i] == N-1:
                return i
        return -1