[算法题] 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 个关于本帖的回复最后回复于 2013-8-16 10:26

	B Color Image Link Quote Code Smilies 高级模式您需要登录后才可以回帖登录 \| 立即注册本版积分规则回帖后跳转到最后一页