有沒有這個特定的編程挑戰的名稱，我們可以做得更好的O（N^2）？

Question

這是問題所在。有N人，其中之一是國王。每個人都知道國王，而國王不認識任何人。有沒有一個名稱或一些理論，如何最好地找出國王的數量是這種情況下，因爲我們有一個函數，確定我是否知道人我知道人j。當然，我們可以簡單地讓每個人先檢查哪些人不認識任何人，然後檢查每個人是否知道哪一個。但這是訂單N^2，我很好奇，如果有更快的事情。在此先感謝

Answer 1

您可以在O(n)時間做到這一點。想象一下，包括國王在內的所有人都可以進入舞廳。我們將其稱爲1到n。訪問人1。詢問他們是否知道人2 - 如果沒有，3等等。他們知道的第一個人v，訪問並詢問他們是否認識人v + 1，如果不是v + 2等等。然後訪問他們認識的第一個人。繼續這樣做，直到您詢問（並可能訪問）n。

既然每個人都知道國王，其中一個人就會把你引導到那個不認識別人的國王身上，因此國王就不能把你引薦給別人。當你開始詢問最後一個人的時候，你會和國王談話。

大致爲：

int find_king() { 
    int visiting = 1; 
    for (int asking_about = 2; asking_about <= n; asking_about++) { 
     if (knows(visiting, asking_about)) { 
      visiting = asking_about; 
     } 
    } 
    return visiting; 
}