研发埠

标题: [算法题] Google/Microsoft : Brain test [打印本页]

作者: 王培培 时间: 2013-8-16 10:16
标题: [算法题] Google/Microsoft : Brain test
一群人参加一个party, 其中有一个人是celebrity, 就是说他不认识所有其他人,所有人都认识他,把这个人找出来, O(n)时间复杂度

作者: 王鹏 时间: 2013-8-16 10:26
这样的，我先问第一个人和第二个人，如果a1认识a2, 那么a1不是celebrity, 如果a1不认识a2, 那么a2就不是celebrity, 这一轮下来可以排除一个人，设另外那个人是p, p再问第三个人a3.....每一轮淘汰一个人，时间复杂度就是O(n)

欢迎光临研发埠 (http://bbs.yanfabu.com/)