关于阿里的明星问题之我见

今天看面试题看到了阿里的明星问题，觉得大家说的太高深了，说一下我的解法吧：

题目：有N个人，其中一个明星和n-1个群众，群众都认识明星，明星不认识任何群众，群众和群众之间的认识关系不知道，现在如果你是机器人R2T2，你每次问一个人是否认识另外一个人的代价为O(1)，试设计一种算法找出明星，并给出时间复杂度（没有复杂度不得分）。

我的解法( 复杂度O(n) )：

// bool known(A, B) 问A认识B不？
Person persons[n];
// init persons
Person p = persons[0];
for(int i = 1; i < n; i++) {
    if(!known(persons[i], p)) { // 不认识，说明p不是明星
      p = persons[i];
    }
    // else 认识，说明persons[i]不是明星
}
// p 就是所求的明星

网址：关于阿里的明星问题之我见 http://c.mxgxt.com/news/view/951273

相关内容

穆里尼奥：我不讨厌阿里但厌倦了关于阿里的问题 我希望他能留队
阿里题目：明星群众问题
【颖晓★被动夫妇】0626关于吧里近期黑粉的问题之我见
关于明星属相的问题
关于明星和黑帮老大的个问题!
关于科学家收入和明星收入的问题，我想谈谈
关于女足世界杯，打破成见的十个问题
阿里扎低迷非因体力原因 麦迪与队友关系没问题
利拉德：和阿德之间从未有过问题
关于《我的阿勒泰》，导演想说的都在这里了

随便看看