gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:12:03 24 4
gpt4 key购买 nike

问题来了。有N个人,其中一个是king。每个人都认识国王,而国王却不认识任何人。鉴于我们有一个函数可以确定人 i 是否认识人 j,是否有关于如何最好地找出国王号码的名称或理论?当然,我们可以简单地为每个人先检查哪些人不认识任何人,然后再检查其中哪些人每个人都知道。但这是 N^2 的顺序,我很好奇是否有更快的东西。提前致谢

最佳答案

您可以在 O(n) 时间内完成此操作。想象一个舞厅,所有人包括国王在内。我们称它们为 1n。访问人员 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;
}

关于algorithm - 这个特定的编程挑战是否有名称,我们可以做些什么比 O(N^2) 更好?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26597830/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com