The Celebrity Problem
派对上有 n 个人，编号从 0 到 n-1。你会得到一个 n × n 矩阵，其中，如果 i 认识 j，则 matrix[i][j] 为 1；如果不认识，则为 0。认识是单向的：i 可以认识 j，而 j 不认识 i。
名人是指每个其他人都认识，但自己不认识任何人的人。返回名人的编号；如果没有名人，则返回 -1。
函数
- matrixinteger-2d-array
- 谁认识谁：第 i 行、第 j 列为 1，表示人物 i 认识人物 j
- 返回值integer
- 名人的号码，如果没有则为 -1
约束条件
2 ≤ n ≤ 150，其中n是行数和列数matrix[i][j]是0或1matrix[i][i] = 0对每个人
示例
- 输入
- matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
- 输出
- 1
- 解释
- 第 1 行全是 0，所以 person 1 谁也不认识。第 1 列在第 0 行和第 2 行的值都是 1，所以另外两个人都认识 person 1。person 1 就是名人。
- 输入
- matrix = [[0, 1], [1, 0]]
- 输出
- -1
- 解释
- 人物 0 认识人物 1，人物 1 也认识人物 0。他们每个人都认识某个人，所以他们都不可能是名人，答案是 -1。
- 输入
- matrix = [[0, 0, 1, 0], [1, 0, 1, 1], [0, 0, 0, 1], [0, 1, 1, 0]]
- 输出
- -1
- 解释
- 其他所有人都认识 person 2，但第 2 行第 3 列的值是 1：person 2 认识 person 3。这就排除了 person 2，而且没有其他人被所有人认识，所以答案是 -1。
进阶
假设每次查找都是一个你必须提出的问题。在最坏情况下，你最少需要提出多少个问题？能否少于 3(n-1)？
提示
逐个打开提示，每个都会多透露一点。
根据定义逐一检查每个人，可能需要读取整个矩阵。选两个人
a和b，查看其中一个单元格matrix[a][b]。无论这个单元格的值是什么，两人中总有一人不可能是名人。在每种情况下，排除的是谁？如果
a认识b，那么a认识某个人，因此可以排除a。如果a不认识b，那么并非所有人都认识b，因此可以排除b。一次查询可以排除一个人，所以经过n-1次查询后，还会剩下一个候选人。在两端各放置一个指针：
a = 0和b = n-1。当a < b时，如果a认识b，就将a向前移动；否则将b向后移动。最后剩下的人只是候选人：返回他之前，先检查他的行和列。
题解
根据定义检查每个人大约需要 2n² 次查找。一个单元格 matrix[a][b] 总能排除 a 和 b 中的一个，因此经过 n-1 次查找后，只剩下一个候选人。然后遍历这个候选人所在的行和列，就能判断他是否是名人。
检查每个人
思路
当第 c 行没有 1（这个人谁也不认识），且除了他们自己所在的行以外，第 c 列的每一行都有 1（每个人都认识他们）时，人物 c 就是名人。依次检查每个人是否符合这个定义，并返回第一个符合的人。
每个人最多需要查找 2(n-1) 次，总共约为 2n² 次：n = 150 意味着约 45,000 次查找。
算法
- 对于从 0 到
n-1的每个人c，检查其他每个人other。 - 如果
matrix[c][other]为 1，或者matrix[other][c]为 0，那么c就不是名人：转到下一个人。 - 如果没有其他人能排除
c，就返回c。 - 如果每个人都不符合条件，就返回 -1。
def findCelebrity(matrix):
n = len(matrix)
for c in range(n):
is_celebrity = True
for other in range(n):
# c must know no one, and everyone else must know c.
if other != c and (matrix[c][other] == 1 or matrix[other][c] == 0):
is_celebrity = False
break
if is_celebrity:
return c
return -1使用栈消除
思路
如果 matrix[a][b] 是 1，a 认识某个人，因此不可能是名人。如果它是 0，a 不认识 b，因此 b 不可能是名人。无论哪种情况，一次查询都会永久排除一个人。把所有人放进栈中，弹出两个人，进行询问，再把仍有可能的人放回栈中：经过 n-1 轮后，就只剩下一个人。
这个人是候选人，不是答案。淘汰过程表明其他人都不可能是名人，但不会检查剩下候选人的行和列。在第三个示例中，剩下的人是 2 号，他认识 3 号，因此检查结果是 -1。检查还需要进行 2(n-1) 次查询，总时间复杂度为 O(n)。
算法
- 把每个人都压入栈中。
- 当栈中有多于一个人时，弹出
a和b。 - 如果
a认识b，就把b放回栈中；否则把a放回栈中。 - 把最后一个人作为候选人。如果此人认识任何人，或者有任何人不认识此人，就返回 -1。
- 否则返回候选人。
def findCelebrity(matrix):
n = len(matrix)
candidates = list(range(n))
# Each question removes one person who cannot be the celebrity.
while len(candidates) > 1:
a = candidates.pop()
b = candidates.pop()
candidates.append(b if matrix[a][b] == 1 else a)
c = candidates[0]
# The survivor is only a candidate: check every other person.
for other in range(n):
if other != c and (matrix[c][other] == 1 or matrix[other][c] == 0):
return -1
return c双指针，然后验证
思路
栈中只保存尚未被排除的人，他们的顺序并不重要。用两个指针代替它：a 指向第一个人，b 指向最后一个人。范围 a 到 b 之外的所有人都已被排除。如果 a 认识 b，就排除 a；否则排除 b。当两个指针相遇时，它们指向的人就是候选人。
在第一个示例中，matrix[0][2] 是 0，所以排除第 2 个人；接着，matrix[0][1] 是 1，所以排除第 0 个人。两个指针在第 1 个人处相遇，他通过了检查。这需要 n-1 次查找，外加至多 2(n-1) 次查找，并且只需额外使用两个整数的内存。
算法
- 将
a = 0和b = n-1设好。 - 当
a < b时：如果matrix[a][b]是 1，就将a加 1；否则将b减 1。 - 候选人是
a。对于其他每个人，检查候选人是否不认识他们，并且他们是否认识候选人。 - 如果所有检查都通过，就返回候选人；否则返回 -1。
def findCelebrity(matrix):
n = len(matrix)
a, b = 0, n - 1
# Each question rules out one of the two people.
while a < b:
if matrix[a][b] == 1:
a += 1 # a knows someone, so a is not the celebrity
else:
b -= 1 # a does not know b, so b is not the celebrity
# a is the only person left who could be the celebrity: check it.
for other in range(n):
if other != a and (matrix[a][other] == 1 or matrix[other][a] == 0):
return -1
return a
易错点和边界情况
- 未检查幸存者就直接返回。在
[[0, 1], [1, 0]]中，幸存者是两个彼此认识的人之一，因此答案是 -1。 - 只检查一侧。第三个示例只在行检查时失败：所有人都认识 person 2，但 person 2 认识 person 3。
- 把对角线也算进去。
matrix[c][c]是 0，因此列检查如果没有跳过other == c，就会排除每个真正的名人。 - 把单元格的含义读反。
matrix[a][b] = 1排除的是a，而不是b。交换两者的角色会丢掉真正的名人。 - 在 Lua 或 R 中返回从 1 开始的索引。人物编号从 0 开始，因此返回前要减去 1。
常见问题3
名人问题的时间复杂度是多少？
消除法的答案运行时间为 O(n)：通过 n-1 次查找找到候选人，并且最多进行 2(n-1) 次检查。双指针版本使用 O(1) 的额外空间，栈版本使用 O(n) 的额外空间。根据定义检查每个人需要 O(n²) 的时间。
可以有不止一位名人吗？
不。如果两个人都是名人，那么每个人都会被所有人认识，所以他们也会互相认识。但名人不认识任何人，因此一场聚会中最多只有一位名人。
名人问题与图有什么关系？
这个矩阵是有向图的邻接矩阵：从 i 到 j 有一条边，表示 i 知道 j。名人是一个出度为 0、入度为 n-1 的节点，也就是通用汇点。统计度数需要读取整个矩阵，而消除法只需读取 O(n) 个单元格就能找到汇点。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def findCelebrity(matrix):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
预期输出
1