[Swift]LeetCode277. 寻找名人 $ Find the Celebrity

佚名 6年前 (2019-04-10) 随笔 1611人围观抢沙发百度已收录

Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 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).

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.

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.

如果你在一个有N个人的聚会上（从0到N-1），找到你的名人，其中可能有一个名人。名人的定义是所有其他人都认识他/她，但他/她不认识他们中的任何一个。

现在你想知道名人是谁，或者确认没有名人。你唯一可以做的就是问这样的问题：“你好，A。你认识B吗？”为了得到A是否知道B的信息，你需要通过尽可能少的提问（在渐近意义上）来找出名人（或者验证没有名人）。

您将得到一个helper函数bool knowns（a，b），该函数告诉您a是否知道b。实现一个函数int findcelebrity（n），您的函数应该最小化要知道的调用数。

注：如果他/她在聚会上，就只有一个名人。如果派对上有名人，请退回名人的标签。如果没有名人，返回-1。

Solution:

 1 class Solution {
 2     func findCelebrity(_ n:Int) -> Int {
 3         var res:Int = 0
 4         for i in 0..<n
 5         {
 6             if knows(res, i) 
 7             {
 8                 res = i
 9             }
10         }
11         for i in 0..<n
12         {
13             if res != i && (knows(res, i) || !knows(i, res))
14             {
15                 return -1
16             }
17         }
18         return res        
19     }
20 }