Python solution: more than 2(n-1) but less than 3(n-1) calls of knows API


  • 0
    W

    More than 2(n-1) but less than 3(n-1) calls of knows API

    class Solution(object):
        def findCelebrity(self, n):
            """
            :type n: int
            :rtype: int
            """
            ruleout = {}
            i, j = 0, 1
            while len(ruleout)<n-1:  # n-1 calls
                if knows(i,j) == True:
                    ruleout.update({i:1})
                    i = j
                    j += 1
                else:
                    ruleout.update({j:1})
                    j += 1
    
            mark = 0
            for num in xrange(n):
                if num not in ruleout:
                    mark = num
                    break
    
            for num in xrange(n):
                if num == mark:
                    continue
                if knows(num, mark) == False or knows(mark, num) == True:  # if the first knows call returns False, the second won't be called.
                    return -1
    
            return mark

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.