[leetcode] 277. Find the Celebrity @ python

原題
https://leetcode.com/problems/find-the-celebrity/
解法
まずn人を遍歴して、可能な候補candを見つけて、有名人の定義によると、有名人はすべての人が彼を知っているが、彼は他の人を知らない.だから、knowns(cand,i)が本物の場合、candはiに更新する必要があります.問題の意味によると、n人の中には最大1人の有名人がいます.それでは、遍歴した後のこのcandが候補です.さらにn人を遍歴し、定義に基づいてcandが有名人かどうかを確定する.
Time: O(2*n) Space: 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
        """
        cand = 0
        for i in range(1, n):
            if knows(cand, i):
                cand = i
                
        for i in range(n):
            if i != cand and (not knows(i, cand) or knows(cand, i)):
                return -1
        return cand