难度: Medium
原题连接
内容描述
Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.
Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).
You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.
Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity's label if there is a celebrity in the party. If there is no celebrity, return -1.
思路 1
celebrity 是 每个人都知道他，而他不认识任何别的人。
如果用图来看，那就每个别的人都有箭头指向c，而c没有任何出去的箭头。
O(N^2)的代码还是还是很容易想到的
但是我们可以有提升，那么就是可以check knows(a,b)，如果 a knows b，那么可以排除a是celebrity，否则可以排除b是celebrity.
最后还要确认一遍是否这个是真的celebrity
总的思路就是说先假设0就是celebrity，然后我们依次遍历下去，第一个不认识cele的人new成为新的cele，因为new不认识原来的cele，并且我们知道如果有的cele的话，那么有且只能有一个cele，所以既然new不认识cele，那cele肯定不是真正的cele，所以目前先假设new是新的cele，继续判断下去。最后我们需要遍历再判断一遍，如果任意cele认识某人或者某人不认识cele的情况出现，就说明没有cele了。
AC代码
时间复杂度: O(n) 空间复杂度: O(1)
# The knows API is already defined for you.
# @param a, person a
# @param b, person b
# @return a boolean, whether a knows b
# def knows(a, b):
class Solution(object):
def findCelebrity(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0:
return -1
cele = 0
for i in range(1, n):
if not knows(i, cele):
cele = i
for i in range(n):
if cele != i:
if not knows(i, cele) or knows(cele, i):
return -1
return cele