阿里笔试题：在n个人中找明星

题目描述：有N个人，其中一个明星和n-1个群众，群众都认识明星，明星不认识任何群众，群众和群众之间的认
识关系不知道，现在如果你是机器人R2T2，你每次问一个人是否认识另外一个人的代价为O(1)，试设计
一种算法找出明星，并给出时间复杂度（没有复杂度不得分）。

----------------------------------------------------------------------------

一种思路：取出两个人，如1号和2号，如果1号认识2号，那么1号不是明星，去除1号；如果1号不认识2号，那么2号不是明星，去除2号。如此比下去，遍历一遍，即可找出明星（剩下的那个）。时间复杂度O(n)。

用两个指针i和j分别指向前、后的两个人，比较一次根据比较结果做一次位置调整。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

bool isRecgn(int i,int j); 

int find(int a[],int n)

{

    int i=0,j=1;

    int cand = i;

    while(j<n)

    {

        if(isRecgn(i,j)){

            cand = j;

            i = j;

            if(++j>n)

                break;

        }

        else{

            cand = i;

            if(++j>n)

                break;

        }

    }

    return cand;

}

网址：阿里笔试题：在n个人中找明星 http://c.mxgxt.com/news/view/877931

相关内容

阿里题目：明星群众问题
明星问题
胜出试镜N套路?
中国昆明犬与比利时马里努阿犬的杂交试验
要不要和明星合影背后，是如何理解1对n的问题
周杰伦，刘翔成考题，这些年这些明星一直“活在”试卷里
明星签名照用什么笔签(找明星签名用什么笔)
【明星找保姆在哪里
姓名笔画配对测试两人关系 名字笔画配对测试两人关系表
江苏省大丰市新丰中学高二语文10月月考试题.doc

随便看看