[leetcode/lintcode 题解] 算法面试真题详解：识别名人

描述
假设你和 n 个人在一个聚会中(标记为 0 到 n - 1)，其中可能存在一个名人。名人的定义是所有其他 n - 1 人都认识他/她，但他/她不知道任何一个。
现在你想要找出这个名人是谁或者验证这个名人不存在。你唯一可以做的事情就是提出如下问题：“你好，A，你认识B吗？” 来获取A是否认识B。您需要通过询问尽可能少的问题(以渐近的意义)来找出名人是谁(或验证其不存在)。
你得到一个辅助函数 bool know(a，b)，它会告诉你A是否知道B.实现一个函数 int findCelebrity(n)，你的函数应该使 knows 的调用次数最少。
如果在这个聚会中有名人， 那么有且只有一个。如果有名人在聚会中则返回名人的标签，如果没有名人，返回 -1。

在线评测地址：领扣题库官网

样例1
2 // 接下来n*(n-1)行
0 knows 1
1 does not know 0
输出： 1
所有人都认识1，而且1不认识其他人。

样例2
3 // 接下来n*(n-1)行
0 does not know 1
0 does not know 2
1 knows 0
1 does not know 2
2 knows 0
2 knows 1
所有人都认识0，而且0不认识其他人。
0不认识1，同时1认识0。
2认识所有人，但是1不认识2。

解题思路
首先loop一遍找到一个人i使得对于所有j(j =i)都不认识i。 然后再loop一遍判断是否有人不认识i或者i认识某个人。

源代码
The knows API is already defined for you.
@param a, person a
@param b, person b
@return a boolean, whether a knows b
you can call Celebrity.knows(a, b)

本文转自网络，原文链接：https://developer.aliyun.com/article/784203
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！