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

╰半夏微凉° 2022-11-24 15:29 94阅读 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 1]  
![n/a][n_a]  
![n/a][n_a 1]

![图 5.4 算法 Celebrity][5.4 _ Celebrity]  
![n/a][n_a 2]

--------------------

## LeetCode\#997. Find the Town Judge ##

【描述】：

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

如果小镇的法官真的存在，那么：

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

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

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

【示例】：

**示例 1：**

输入：N = 2, trust = [[1,2]]
    输出：2

**示例 2：**

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

**示例 3：**

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

**示例 4：**

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

**示例 5：**

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

【提示】：

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

**Solution:**

class Solution:
        def findJudge(self, N: int, trust: List[List[int]]) -> int:
            if N <= 1:
                pass
    
            peoples = collections.defaultdict(set)
            for _from, _to in trust:
                peoples[_from].add(_to)
    
            retain = 0
            a = 1
            b = 2
            retain = b if b in peoples[a] else a
            for judge in range(3, N+1):
                retain = retain if retain in peoples[judge] else judge
    
            citizen = 1
            while citizen <= N:
                if citizen != retain and retain not in peoples[citizen]:
                    return -1
                citizen += 1
    
            return retain if not peoples[retain] else -1

*Submission:*

![N/A][N_A 2]

> 更快的解法？  
> 直接根据 trust 数组操作！
> 
>     class Solution:
>         def findJudge(self, N: int, trust: List[List[int]]) -> int:
>             dst = [1]*N
>             for _from, _to in trust:
>                 dst[_from-1] = 0
>             _sum = sum(dst)
>             if _sum > 1 or _sum == 0:
>                 return -1
>     
>             judge = dst.index(1) + 1
>             for _from, _to in trust:
>                 if _to == judge:
>                     dst[_from-1] = 1
>     
>             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 社会名流问题 ↩︎

[N_A]: /images/20221124/9f8101dd23ba4d00857acc7d3189b245.png
[N_A 1]: /images/20221124/f84f5f35c5224e8e95d20b79f80dffd6.png
[n_a]: /images/20221124/a67a1ff95aa44463a511863612960934.png
[n_a 1]: /images/20221124/0ce872bd791248999fa252e44e10ba2e.png
[5.4 _ Celebrity]: /images/20221124/6335758b118849f888b96434f2ac9bcf.png
[n_a 2]: /images/20221124/5bcbd267304344ea830f79b055ca9978.png
[N_A 2]: /images/20221124/1b8db6c45bd14646bc401ff72649a257.png
[----]: https://blog.csdn.net/zjx409/article/details/21985195