Find the Celebrity

Suppose you are at a party withnpeople (labeled from0ton - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the othern - 1people 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 functionbool knows(a, b)which tells you whether A knows B. Implement a functionint findCelebrity(n), your function should minimize the number of calls toknows.

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个或0个名人，给定了一个API函数，输入a和b，用来判断a是否认识b，让我们尽可能少的调用这个函数，来找出人群中的名人。我们用for loop一个人一个人的验证其是否为名人，对于候选者i，我们遍历所有其他人j，如果i认识j，或者j不认识i，说明i不可能是名人，那么break，跳出循环，然后验证下一个候选者，如果loop j里面的条件全都不满足，用else返回i就是我们要找的人，如果遍历完所有人没有找到名人，返回-1，要注意for else loop的用法：

For loops also have anelseclause which most of us are unfamiliar with. Theelseclause executes when the loop completes normally. This means that the loop did not encounter anybreak. They are really useful once you understand where to use them. I myself came to know about them a lot later.

The common construct is to run a loop and search for an item. If the item is found, we break the loop usingbreak. There are two scenarios in which the loop may end. The first one is when the item is found andbreakis encountered. The second scenario is that the loop ends. Now we may want to know which one of these is the reason for a loops completion. One method is to set a flag and then check it once the loop ends. Another is to use theelseclause.

两个for/else loop的例子：

for item in container:
    if search_something(item):
        # Found it!
        process(item)
        break
else:
    # Didn't find anything..
    not_found_in_container()

It finds factors for numbers between 2 to 10. Now for the fun part. We can add an additionalelseblock which catches the numbers which are prime and tells us so:

for n in range(2, 10):
    for x in range(2, n):
        if n % x == 0:
            print( n, 'equals', x, '*', n/x)
            break
    else:
        # loop fell through without finding a factor
        print(n, 'is a prime number')

# 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
        """
        for i in xrange(n):
            for j in xrange(n):
                if i==j:
                    continue
                if [knows(i,j), knows(j,i)] != [False, True]:
                    break
            else:
                return i
        return -1