懒人读算法(一)-寻找名人

本文主要是介绍懒人读算法(一)-寻找名人，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

趣味题:

假设一场聚会有n个人，他们中间可能存在一个名人。名人的定义是在场的人都认识他，而他却不认识所有人。
已知条件:
1.函数knows(a,b)告诉你a是否认识b，返回bool值

你要做的事:确定这场聚会是否有名人的存在,如果不存在则return -1

答案:

public class Solution extends Relation {public int findCelebrity(int n) {//initialize candidate to 0int candidate = 0;//find viable candidatefor(int i = 1; i < n; i++) {if(knows(candidate, i)) {candidate = i;}}//check that everyone else knows the candidatefor(int i = 0; i < n; i++) {//if the candidate knows the current person or the current person does not know the candidate, return -1 (candidate is not a celebrity)if(i != candidate && knows(candidate, i) || !knows(i, candidate)) {return -1;}}//return the celebrityreturn candidate;}}

算法解析:因为名人不认识所有人，所有人认识名人，可以根据这个性质，来遍历所有人.

     int candidate = 0;//find viable candidatefor(int i = 1; i < n; i++) {if(knows(candidate, i)) {candidate = i;}}

代码解释:假设3号是名人,总共5个人。因为所有人认识名人，所以knows(candidate, 3)肯定成立,潜在的名人candidate=3。而名人不认识所有人，所以knows(3,i)不可能再成立.由此可以确定名人是谁。

但是根据这个条件还不能完全确定这个人是不是名人。因为以上条件仅仅确定名人不认识剩下的所有人。
所以要再来一次遍历

        //check that everyone else knows the candidatefor(int i = 0; i < n; i++) {if(i != candidate && knows(candidate, i) || !knows(i, candidate)) {return -1;}}

代码解释:如果当前的人不是名人且名人如果认识其中任何一个人，或其他人不认识名人，则说明不存在名人.

本题解析：抓住题干信息，考虑问题全面即可解答

这篇关于懒人读算法(一)-寻找名人的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---