Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
镇上一共n个人,给出一些trust pair,trust[i]=[ai, bi],表示ai信任bi,镇上有一位法官,法官被所有人信任,且不信任任何人,如果可以通过这些trust pair判断第几个人是法官,则输出,否则输出-1
用fg_be_trusted标记每个人被几个人信任,fg_trust标记每个人信任几个其他人,如果法官存在,则fg_trust[i]=0,fg_be_trusted[i]=n-1


 1 #997
 2 #Runtime: 1407 ms (Beats 26.42%)
 3 #Memory: 18.5 MB (Beats 91.6%)
 4 
 5 class Solution(object):
 6     def findJudge(self, n, trust):
 7         """
 8         :type n: int
 9         :type trust: List[List[int]]
10         :rtype: int
11         """
12         fg_trust = [0] * (n + 1)
13         fg_be_trusted = [0] * (n + 1)
14         for i,j in trust:
15             fg_be_trusted[j] += 1
16             fg_trust[i] += 1
17         cnt = 0
18         for i in range(1, n + 1):
19             if fg_trust[i] == 0 and fg_be_trusted[i] == n - 1:
20                 cnt += 1
21                 fg = i
22         if cnt == 1:
23             return fg
24         return -1

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理