给定一组 n 个人，A 可能认识也可能不认识 B(同样，A 认识 B 并不意味着 B 认识 A)。由 nxn bool 矩阵定义的所有熟人关系。
让我们将名人定义为人人皆知，但无人知晓的人。
任务是提出一个算法，该算法需要 O(n) 时间和 O(1) 额外空间来查找集合中的名人或声明该集合不包含任何名人。
首先，我的印象是，写这篇文章的人有意扰乱那些将要解决这个问题的人的头脑。
我认为，这里的线性时间意味着我们可以将时间与输入大小(实际上是 n*n)进行线性比较。
然后提出二次时间算法似乎是微不足道的任务。另一方面，如果我们假设我之前的陈述有误，我不相信在时间为 O(k) 的边为 k 的未排序矩阵中可以找到很多...
我将在这里留下二次时间算法的草稿:
for x in range(0,side-1):
knowingAmount = sumAlongColumn(x)
if knowingAmount == side:
celebritySuspectKnows = sumAlongRow(x)
if celebritySuspectKnows == 1:
return x
return -1
所以，如果你们在这里帮助我，我将不胜感激。我是否正确地解释了这个具有时间复杂度要求的警告，或者这里存在更有效的算法？
最佳答案
对于每个人:
如果我们没有潜在的名人，就让这个人成为潜在的名人。
如果潜在名人和此人都不认识，或者他们都认识，请重置潜在名人。
如果潜在名人认识此人，但相反，则让此人成为新的潜在名人。
或者，简化:
让第一个人成为潜在的名人。
对于每个人:(从第二个开始)
- 如果潜在名人认识此人，则让此人成为新的潜在名人。
完成后，如果我们有潜在的名人，请再次检查此人是否不认识其他人以及是否每个人都认识他们，以确保他们确实是名人。
复杂度: O(n) 时间，O(1) 空间。
证明正确性的关键是:
如果那个人是名人，我们就不能继续前进，因为继续前进的唯一标准是了解其他人，这对名人来说是不可能的。
如果有名人，我们总是会切换到名人，因为我们会遍历所有人，如果一个人认识这个人，我们总是会切换，这对于所有其他人来说都是如此。
但是，如果没有名人，我们最后仍然会有一个(非名人)候选人(假设我们很容易提名某人为潜在名人)，所以我们需要确保候选人是名人。
关于algorithm - 在线性时间内解决相识任务，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23649675/