[leetcode/lintcode 題解] 算法面試真題詳解：識别名人

描述

假設你和 n 個人在一個聚會中(标記為 0 到 n - 1)，其中可能存在一個名人。名人的定義是所有其他 n - 1 人都認識他/她，但他/她不知道任何一個。

現在你想要找出這個名人是誰或者驗證這個名人不存在。你唯一可以做的事情就是提出如下問題：“你好，A，你認識B嗎？” 來擷取A是否認識B。您需要通過詢問盡可能少的問題(以漸近的意義)來找出名人是誰(或驗證其不存在)。

你得到一個輔助函數 bool know(a，b)，它會告訴你A是否知道B.實作一個函數 int findCelebrity(n)，你的函數應該使 knows 的調用次數最少。

如果在這個聚會中有名人， 那麼有且隻有一個。如果有名人在聚會中則傳回名人的标簽，如果沒有名人，傳回 -1。

線上評測位址：

領扣題庫官網

樣例1
輸入：
2 // 接下來n*(n-1)行
0 knows 1
1 does not know 0
輸出： 1
解釋：
所有人都認識1，而且1不認識其他人。           

樣例2
輸入：
3 // 接下來n*(n-1)行
0 does not know 1
0 does not know 2
1 knows 0
1 does not know 2
2 knows 0
2 knows 1
輸出：0
解釋：
所有人都認識0，而且0不認識其他人。
0不認識1，同時1認識0。
2認識所有人，但是1不認識2。           

解題思路

首先loop一遍找到一個人i使得對于所有j(j>=i)都不認識i。 然後再loop一遍判斷是否有人不認識i或者i認識某個人。

源代碼
"""
The knows API is already defined for you.
@param a, person a
@param b, person b
@return a boolean, whether a knows b
you can call Celebrity.knows(a, b)
"""


class Solution:
    # @param {int} n a party with n people
    # @return {int} the celebrity's label or -1
    def findCelebrity(self, n):
        celeb = 0
        
        for i in range(1, n):
            if Celebrity.knows(celeb, i):
                celeb = i
        
        # Check if the final candicate is the celebrity
        for i in range(n):
            if celeb != i and Celebrity.knows(celeb, i):
                return -1
            if celeb != i and not Celebrity.knows(i, celeb):
                return -1
        
        return celeb           

更多題解參考：

九章官網solution