【Leetcode】997. Find the Town Judge(找到小镇法官) - 社会名流问题

╰半夏微凉° 2022-11-24 15:29 156阅读 0赞

Desc: N/A

Overview

    • 社会名流问题
    • LeetCode#997. Find the Town Judge
    • Reference

社会名流问题

接下来的这个例子是算法设计中的一个常见习题,这是一个不需要扫描所有数据(或者绝大部分)就能得到解答的很好例子。

在n个人中,有一个被所有人知道但却不知道别人的人,这个人被定义为社会名流。现在的问题是如果存在,试找出社会名流。你可以使用的唯一方式是询问:“对不起,请问你知道某某人吗?”(假定所有回答都正确,甚至这位社会名流也将回答。)我们的目标是将问题的数目最小化。由于有 n ( n − 1 ) / 2 n(n-1)/2 n(n−1)/2 对人,如果提问是随意的,那么在最坏情况下可能需要问 n ( n − 1 ) n(n-1) n(n−1) 个问题。在最坏情况下,应该如何做并不那么明显。

可以使用图论来表示该问题,使用一个有向图,每个顶点表示一个人,如果 A 知道 B,则从 A 到 B 有一条边。一个社会名流对应于图中的 汇点(在此无双关语之意)。一个汇点是入度为 n − 1 n-1 n−1 而出度为 0 的顶点。注意一个图中之多有一个汇点。问题的输入对应于一个 n × n n \times n n×n 连结矩阵(如果第 i i i 个人知道第 j j j 个人,则 i j ij ij 项为 1, 否则为 0。)1

N/A
N/A
n/a
n/a

图 5.4 算法 Celebrity
n/a


LeetCode#997. Find the Town Judge

【描述】:

在一个小镇里,按从 1N 标记了 N 个人。传言称,这些人中有一个是小镇上的秘密法官。

如果小镇的法官真的存在,那么:

  1. 小镇的法官不相信任何人。
  2. 每个人(除了小镇法官外)都信任小镇的法官。
  3. 只有一个人同时满足属性 1 和属性 2 。

给定数组 trust,该数组由信任对 trust[i] = [a, b] 组成,表示标记为 a 的人信任标记为 b 的人。

如果小镇存在秘密法官并且可以确定他的身份,请返回该法官的标记。否则,返回 -1

【示例】:

示例 1:

  1. 输入:N = 2, trust = [[1,2]]
  2. 输出:2

示例 2:

  1. 输入:N = 3, trust = [[1,3],[2,3]]
  2. 输出:3

示例 3:

  1. 输入:N = 3, trust = [[1,3],[2,3],[3,1]]
  2. 输出:-1

示例 4:

  1. 输入:N = 3, trust = [[1,2],[2,3]]
  2. 输出:-1

示例 5:

  1. 输入:N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
  2. 输出:3

【提示】:

  • 1 <= N <= 1000
  • trust.length <= 10000
  • trust[i] 是完全不同的
  • trust[i][0] != trust[i][1]
  • 1 <= trust[i][0], trust[i][1] <= N

Solution:

  1. class Solution:
  2. def findJudge(self, N: int, trust: List[List[int]]) -> int:
  3. if N <= 1:
  4. pass
  5. peoples = collections.defaultdict(set)
  6. for _from, _to in trust:
  7. peoples[_from].add(_to)
  8. retain = 0
  9. a = 1
  10. b = 2
  11. retain = b if b in peoples[a] else a
  12. for judge in range(3, N+1):
  13. retain = retain if retain in peoples[judge] else judge
  14. citizen = 1
  15. while citizen <= N:
  16. if citizen != retain and retain not in peoples[citizen]:
  17. return -1
  18. citizen += 1
  19. return retain if not peoples[retain] else -1

Submission:

N/A

更快的解法?
直接根据 trust 数组操作!

  1. class Solution:
  2. def findJudge(self, N: int, trust: List[List[int]]) -> int:
  3. dst = [1]*N
  4. for _from, _to in trust:
  5. dst[_from-1] = 0
  6. _sum = sum(dst)
  7. if _sum > 1 or _sum == 0:
  8. return -1
  9. judge = dst.index(1) + 1
  10. for _from, _to in trust:
  11. if _to == judge:
  12. dst[_from-1] = 1
  13. return judge if all(dst) else -1

应该是有快了一点点。

Runtime: 948 ms, faster than 38.44%; Memory Usage: 18.3 MB, less than 20.55%

Next Challenge:
https://leetcode.com/problems/find-the-celebrity/ (Subscribe)

Reference:

  • 社会名流问题的解答——算法引论学习
  • https://www.cnblogs.com/grandyang/p/5310649.html

Reference


  1. 《算法引论》&5.5 社会名流问题 ↩︎

发表评论

表情:
评论列表 (有 0 条评论,156人围观)

还没有评论,来说两句吧...

相关阅读

    相关 997. 找到小镇法官

    在一个小镇里,按从 `1` 到 `N` 标记了 `N` 个人。传言称,这些人中有一个是小镇上的秘密法官。 如果小镇的法官真的存在,那么: 1. 小镇的法官不相信任何人。