algorithm - 这个特定的编程挑战是否有名称，我们可以做些什么比 O(N^2) 更好？

Question

问题来了。有N个人，其中一个是king。每个人都认识国王，而国王却不认识任何人。鉴于我们有一个函数可以确定人 i 是否认识人 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;
}