Description
In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge.
If the town judge exists, then:
- The town judge trusts nobody.
- Everybody (except for the town judge) trusts the town judge.
- There is exactly one person that satisfies properties 1 and 2.
You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b.
If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1.
在一个小镇里，按从 1 到 N 标记了 N 个人。传言称，这些人中有一个是小镇上的秘密法官。
如果小镇的法官真的存在，那么：
- 小镇的法官不相信任何人。
- 每个人（除了小镇法官外）都信任小镇的法官。
- 只有一个人同时满足属性 1 和属性 2 。
给定数组 trust，该数组由信任对 trust[i] = [a, b] 组成，表示标记为 a 的人信任标记为 b 的人。
如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的标记。否则，返回 -1。
题目链接：https://leetcode.com/problems/find-the-town-judge/
Difficulty: easy
Example 1:
Input: N = 2, trust = [[1,2]]
Output: 2
Example 2:
Input: N = 3, trust = [[1,3],[2,3]]
Output: 3
Example 3:
Input: N = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1
Example 4:
Input: N = 3, trust = [[1,2],[2,3]]
Output: -1
Example 5:
Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3
Note:
- 1 <= N <= 1000
- trust.length <= 10000
- trust[i] are all different
- trust[i][0] != trust[i][1]
- 1 <= trust[i][0], trust[i][1] <= N
分析
- 初始化字典A，每一项代表每个人被那些人信任；
- 对于任意trust，a信任b，从A中删除a；
- 同时若b在A中，则将a添加为信任b的list中；
- 返回A中被信任N-1次的人，若无，返回-1。
参考代码
class Solution:
def findJudge(self, N: int, trust: List[List[int]]) -> int:
A={}
for i in range(N):
A[i+1]=[]
for t in trust:
x,y=t
if(x in A):
A.pop(x)
if(y in A):
A[y].append(x)
for a in A:
if(len(A[a])==N-1):
return a
return -1