从零开始找出“聚会隐藏王”！Swift 解密 LeetCode 名人问题
文章目录
摘要描述举个例子：
题解答案（Swift）题解代码分析第一步：候选人筛选第二步：验证候选人
示例测试及结果时间复杂度空间复杂度实际场景中的应用QA 环节Q1：如果有多个名人怎么办？Q2：如何避免多次调用 `knows()` 函数？
总结未来展望
摘要
在一群人中找到“名人”听起来像是八卦聚会的开场话题，但在 LeetCode 上，它其实是一个非常经典的逻辑推理问题，涉及图论中的入度和出度分析。这篇文章将带你一步步理解这道题的本质、实现它的高效解法，并用 Swift 写出一套可运行的代码。最后我们还会分析它的性能，并探讨这类问题在实际生活或系统设计中可能的应用。
描述
题目要求你在一个 n 个人的聚会中找出所谓的“名人”。每个人被编号为 0 到 n-1。你可以调用一个函数 knows(a, b) 来判断 a 是否认识 b。
题设的定义是：
名人不会认识任何人（除了自己）。所有人都认识名人。
你的任务是找出这位名人，或者如果没有名人，则返回 -1。
举个例子：
输入: n = 3，knows关系如下：
Person 0 knows 1 and 2
Person 1 knows 2
Person 2 knows no one
输出: 2
解释: 2 是名人，其他人都认识他，他不认识任何人
题解答案（Swift）
class Solution {
private var knowsMatrix: [[Bool]] = []
init(knowsMatrix: [[Bool]]) {
self.knowsMatrix = knowsMatrix
}
private func knows(_ a: Int, _ b: Int) -> Bool {
return knowsMatrix[a][b]
}
func findCelebrity(_ n: Int) -> Int {
var candidate = 0
// 第一次遍历找候选人
for i in 1.. if knows(candidate, i) { candidate = i } } // 第二次确认候选人是否是名人 for i in 0.. if i != candidate { if knows(candidate, i) || !knows(i, candidate) { return -1 } } } return candidate } } 题解代码分析 第一步：候选人筛选 我们一开始假设 0 是名人，然后从 1 到 n-1 遍历： 如果 candidate 认识 i，说明 candidate 不可能是名人，把 candidate 设为 i。如果 candidate 不认识 i，则保留当前的候选人。 为什么这么做有效？因为如果某人认识另一个人，那他肯定不是名人；而如果他不认识另一个人，那另一个人也不能是名人（因为名人应该被所有人认识）。 第二步：验证候选人 我们已经筛选出一个可能的候选人，还需要再次遍历确认： 他不应该认识任何人。所有人都应该认识他。 只要有一个不满足，这个人就不是名人，直接返回 -1。 示例测试及结果 let matrix = [ [false, true, true], [false, false, true], [false, false, false] ] let solution = Solution(knowsMatrix: matrix) print(solution.findCelebrity(3)) // 输出 2 在这个示例中： 0 认识 1 和 2。1 认识 2。2 谁都不认识。 很明显，2 被所有人认识，且自己不认识任何人，所以他就是名人。 时间复杂度 候选人筛选：O(n)验证候选人：O(n) 总的时间复杂度为 O(n)，远优于暴力的 O(n²) 方案。 空间复杂度 我们没有使用额外空间（除了常量变量），所以空间复杂度是 O(1)。 实际场景中的应用 这道题虽然出现在算法平台上，但类似的逻辑常常出现在实际系统中，比如： 在社交网络中判断某个账号是否是“信息中心”。在组织结构图中找出某位只被汇报、却不汇报任何人的高管。在事件链中寻找最终的“接收者”或根节点。 QA 环节 Q1：如果有多个名人怎么办？ 答： 根据题目要求，最多只有一个名人，所以我们不考虑多个名人的情况。但在实际系统中，可能需要返回一个列表，可以在验证阶段收集所有满足条件的节点。 Q2：如何避免多次调用 knows() 函数？ 答： 可以做记忆化缓存（比如用字典存 knows(i, j) 的结果），在大规模系统中这是非常重要的优化。 总结 “名人问题”本质上是图论中的一个“入度为 n-1，出度为 0”的节点查找问题。这题不仅考验你对关系判断的抽象能力，也考验你在有限信息下进行逻辑推理的能力。Swift 在处理数组和逻辑结构时有很好的表达力，是非常适合实现这类算法的语言。 未来展望 名人问题只是“信息流向分析”的冰山一角。如果你在做知识图谱、社交图、组织图、推荐系统，其实都能用上类似的入度-出度分析方法。后续我们还可以扩展到带权图、多层图等高级话题。