是否有这个特定编程挑战的名称,我们可以做得更好O(N ^ 2)？

Question

这是问题所在.有N个人,其中一个是国王.每个人都认识国王,而国王却不认识任何人.是否有一个名称或一些理论如何最好地找出国王的数量是这种情况,因为我们有一个功能,以确定我是否知道人j.当然,我们可以简单地为每个人检查哪些人不认识任何人,然后检查每个人都知道哪一个.但这是订单N ^ 2,如果有更快的东西,我很好奇.提前致谢

Answer 1

你可以及时做到这一点O(n).想象一下与包括国王在内的所有人的舞厅.我们会打电话给他们1通过n.拜访人1.问他们是否认识某人2- 如果没有,3等等.他们认识的第一个人,人v,访问并询问他们是否认识v + 1,如果不认识v + 2,等等.然后拜访他们认识的第一个人.继续这样做,直到你询问(并可能访问)n.

既然每个人都认识国王,其中一个人就会把你引导给那个不认识其他人的国王,因此国王不能把你推荐给其他任何人.在你询问最后一个人,一个人之后n,你将与国王交谈.

大致:

int find_king() {
    int visiting = 1;
    for (int asking_about = 2; asking_about <= n; asking_about++) {
        if (knows(visiting, asking_about)) {
            visiting = asking_about;
        }
    }
    return visiting;
}