王培培 发表于 2013-8-16 10:16:50

[算法题] Google/Microsoft : Brain test 

一群人参加一个party, 其中有一个人是celebrity, 就是说他不认识所有其他人,所有人都认识他,把这个人找出来, O(n)时间复杂度

王鹏 发表于 2013-8-16 10:26:59

这样的，我先问第一个人和第二个人，如果a1认识a2, 那么a1不是celebrity, 如果a1不认识a2, 那么a2就不是celebrity, 这一轮下来可以排除一个人，设另外那个人是p, p再问第三个人a3.....每一轮淘汰一个人，时间复杂度就是O(n)
页: [1]
查看完整版本: [算法题] Google/Microsoft : Brain test