在一组人中寻找“星星”算法的时间复杂度

Question

我遇到了一个问题，要求在一系列正常人中找到一颗星。明星的定义是“不认识任何人，但每个人都认识他们的人”。输入是n个人的数组，你可以做的基本测试是问一个人i“你认识j人吗”，如果他们认识他，他们回答"true“，如果不认识，回答false。问最少的问题。

我为这个算法找到的最坏情况的最佳解决方案是O(nlog) (你问一个人他们是否认识他们后面的人i+1，如果他们知道，你就把他们从潜在的星星中剔除，如果不认识，你就把i+1从潜在的星星中剔除，每次遍历数组，我可以将潜在星星的数量减半)，但摘录说，在最坏的情况下，证明它可以用O(n)完成

Answer 1

明星的定义是“不认识任何人，但每个人都认识他们的人

根据这个定义，在一群人中最多只能有一个“明星”。如果有不止一颗星，那么它们都必须认识另一颗星，否则另一颗星就不是星，但它们本身就不是星。

因此，有两个子问题。

1. 寻找潜在的明星。

如果有多个这样的人，就没有星星；如果恰好有一个这样的人：

1. 检查是否每个人都认识这个人。

第一部分可以用你提出的算法来完成。不管你问A是否知道B，那么C是否知道D等等，或者如果你问A或B的“赢家”是否知道C等等:因为你每次问的时候都会删除一个“候选”，所以你最多需要O(n)步，而不是O(nlogn)步。在那之后，你只剩下一个潜在的明星，可以做第二步，这是一个简单的循环，在组中的所有其他人。

两个步骤的时间复杂度都是O(n)，总共(仍然) O(n)。