打了指纹，但状态还是Initial review - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>EB23 - 劳工卡

打了指纹，但状态还是Initial review

打了指纹，但状态还是Initial review# EB23 - 劳工卡

b*w2014-05-07 07:05

1 楼

昨天居然又被问到了：
屋子里有n个人，如果i 认识 j, 那么他们之间有条directed edge. 如果有这么一个人
：大家都认识他，但他不认识其他任何人，我们叫他celebrity.
如果在O(n)时间找出celebrity?
谢谢

l*02014-05-07 07:05

2 楼

EB2->EB3，有影响吗？

l*82014-05-07 07:05

3 楼

DFS ?

【在 b*****w 的大作中提到】

: 昨天居然又被问到了：
: 屋子里有n个人，如果i 认识 j, 那么他们之间有条directed edge. 如果有这么一个人
: ：大家都认识他，但他不认识其他任何人，我们叫他celebrity.
: 如果在O(n)时间找出celebrity?
: 谢谢

p*22014-05-07 07:05

4 楼

建个图之有入没有出就是了

昨天居然又被问到了：屋子里有n个人，如果i 认识 j, 那么他们之间有条directed
edge. 如果有这么一个人：大家都认识他，但他不认识其他任何人，我们叫他celebr..
......
★ Sent from iPhone App: iReader Mitbbs Lite 7.52

【在 b*****w 的大作中提到】

l*82014-05-07 07:05

5 楼

How does the input data structure store the "directed edges"?

【在 b*****w 的大作中提到】

q*x2014-05-07 07:05

6 楼

google

【在 b*****w 的大作中提到】

l*82014-05-07 07:05

7 楼

问题描述：在一个聚会上有 n 个人，其中有一个名人，大家都认识他，但他却不认识
所有其他人。现在请你只通过询问来宾 x 是不是认识来宾 y 的方式把这个名人找出来
。最多只能使用 O(n) 次询问。

x*a2014-05-07 07:05

8 楼

不重复的问下去，一定会问到这个名人,
这个名人没有下一个,所以stop

【在 l*********8 的大作中提到】

: 问题描述：在一个聚会上有 n 个人，其中有一个名人，大家都认识他，但他却不认识
: 所有其他人。现在请你只通过询问来宾 x 是不是认识来宾 y 的方式把这个名人找出来
: 。最多只能使用 O(n) 次询问。

p*22014-05-07 07:05

9 楼

认识淘汰x不认识淘汰y

问题描述：在一个聚会上有 n 个人，其中有一个名人，大家都认识他，但他却不认识
所有其他人。现在请你只通过询问来宾 x 是不是认识来宾 y 的方式把这个名人找出来
。最多只能使用........
★ Sent from iPhone App: iReader Mitbbs Lite 7.52

【在 l*********8 的大作中提到】

c*p2014-05-07 07:05

10 楼

建图的worst case是O(n^2)吧

..

【在 p*****2 的大作中提到】

: 建个图之有入没有出就是了
:
: 昨天居然又被问到了：屋子里有n个人，如果i 认识 j, 那么他们之间有条directed
: edge. 如果有这么一个人：大家都认识他，但他不认识其他任何人，我们叫他celebr..
: ......
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.52

c*p2014-05-07 07:05

11 楼

这样没法确定所有人都认识名人。

【在 p*****2 的大作中提到】

: 认识淘汰x不认识淘汰y
:
: 问题描述：在一个聚会上有 n 个人，其中有一个名人，大家都认识他，但他却不认识
: 所有其他人。现在请你只通过询问来宾 x 是不是认识来宾 y 的方式把这个名人找出来
: 。最多只能使用........
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.52

p*22014-05-07 07:05

12 楼

Assume 有一个吧

这样没法确定所有人都认识名人。
★ Sent from iPhone App: iReader Mitbbs Lite 7.52

【在 c****p 的大作中提到】

: 这样没法确定所有人都认识名人。

k*i2014-05-07 07:05

13 楼

This is the solution:
Assume 1-10 persons:
ask 1: whom do you know? 1 may answer: 3; (We can exclude 1)
ask 3: whom do you know excpt 1? 3 may answer: 6; (We can exclude 1,3)
ask 6: whom do you know except 1,3? 6 may answer: 4; (Exclude 1,3,6)
ask 4: whom do you know except 1,3,6? 4 may answer: 9; (Exclude 1,3,6,9)
ask 9: ...
then someone will answer: I know nobody.
The persons in "except" list are not qualified for celebrity, because they know someone else.

【在 b*****w 的大作中提到】

g*x2014-05-07 07:05

14 楼

"他却不认识所有其他人。"
是指他不认识任何一个其他的人，还是他认识some of them?

【在 p*****2 的大作中提到】

e*l2014-05-07 07:05

15 楼

即使不assume存在一个也可以O(n)找到答案。如果存在，只能有一个。
用上面的x,y淘汰法可以O(n)确定一个candidate，然后问其余n-1个人是不是认识这个
candidate，如果都认识，那就找到了名人。否则名人就不存在。

【在 p*****2 的大作中提到】

: Assume 有一个吧
:
: 这样没法确定所有人都认识名人。
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.52

e*i2014-05-07 07:05

16 楼

suppose the people are: A, B, C, D, E, ...
Ask if A knows B, remove A if yes, otherwise remove B
Ask if the remaining one of (A,B) knows C, remove the one in (A,B) if yes,
otherwise remove C,
......
In each "ask" we exclude one people. Keep doing this until there is only one
left, which is the celebrity.
Time = N asks.
The precondition is: there must be one and only one celebrity.
If there may be no celebrity, you can double check by asking if the final
one doesn't knows anyone AND if all the others knows the final one.
Time = 3*N-1 asks.

d*n2014-05-07 07:05

17 楼

根据题目条件这个名人必然只有一个，所以只需要找到唯一的一个人都不认识的人即
可。
但是这好像过于trivial了。

k*i2014-05-07 07:05

18 楼

我想这个方法可以在O(n)内识别出来。

【在 k***i 的大作中提到】

: This is the solution:
: Assume 1-10 persons:
: ask 1: whom do you know? 1 may answer: 3; (We can exclude 1)
: ask 3: whom do you know excpt 1? 3 may answer: 6; (We can exclude 1,3)
: ask 6: whom do you know except 1,3? 6 may answer: 4; (Exclude 1,3,6)
: ask 4: whom do you know except 1,3,6? 4 may answer: 9; (Exclude 1,3,6,9)
: ask 9: ...
: then someone will answer: I know nobody.
: The persons in "except" list are not qualified for celebrity, because they know someone else.

d*n2014-05-07 07:05

19 楼

加上这个限制貌似题目更make sense一些。

【在 l*********8 的大作中提到】

y*n2014-05-07 07:05

20 楼

妙法！

【在 p*****2 的大作中提到】

p*22014-05-07 07:05

21 楼

是。

【在 e***l 的大作中提到】

:
: 即使不assume存在一个也可以O(n)找到答案。如果存在，只能有一个。
: 用上面的x,y淘汰法可以O(n)确定一个candidate，然后问其余n-1个人是不是认识这个
: candidate，如果都认识，那就找到了名人。否则名人就不存在。

c*p2014-05-07 07:05

22 楼

问其余n-1个人是不是认识这个candidate的复杂度，如果不用hash表的话，不是O(n)吧？
如果用hash表的话，建表的代价就是O(n^2)了。

【在 e***l 的大作中提到】

c*p2014-05-07 07:05

23 楼

关键问题是：
问A是否知道B的代价是O(1)么？

one

【在 e****i 的大作中提到】

: suppose the people are: A, B, C, D, E, ...
: Ask if A knows B, remove A if yes, otherwise remove B
: Ask if the remaining one of (A,B) knows C, remove the one in (A,B) if yes,
: otherwise remove C,
: ......
: In each "ask" we exclude one people. Keep doing this until there is only one
: left, which is the celebrity.
: Time = N asks.
: The precondition is: there must be one and only one celebrity.
: If there may be no celebrity, you can double check by asking if the final

e*l2014-05-07 07:05

24 楼

应该需要邻接矩阵。或者像后面那个描述，可以直接问x是否认识y，也就是O(1)。

f*22014-05-07 07:05

25 楼

问x，认识y吗？如果认识，x肯定不是名人；如果不认识，y肯定不是名人。所以每次
ask必然淘汰一次，经过最多n次ask，肯定能找出名人。
问一次的代价应该是O（1）吧，要不N代表什么。。。

z*y2014-05-07 07:05

26 楼

很简单的题，由此开始满十个包子我贴个答案

c*92014-05-07 07:05

27 楼

可以用对每个人用count，如果有人认识他就++，认识别人就--，最后谁的count是n就
是那个人

z*y2014-05-07 07:05

28 楼

你这个就是统计入度和出度，复杂度O(n*n)
还是给包子等答案吧

【在 c****9 的大作中提到】

: 可以用对每个人用count，如果有人认识他就++，认识别人就--，最后谁的count是n就
: 是那个人

u*r2014-05-07 07:05

29 楼

同意这个。每次淘汰一个人，问n－１次最后只能剩下一个。
柯南说得好，真相只有一个，排除所有不可能，剩下的就是答案。

【在 p*****2 的大作中提到】

l*82014-05-07 07:05

30 楼

int FindCelibrity(bool ** know, int n)
{
if (know == NULL || n<1) return -1;
int cel=0;
for (int i=1; iif (know[cel][i])
cel = i;
return cel;
}

t*e2014-05-07 07:05

31 楼

Since there is just one guy do not know anybody. Just go through everyone,
count number of people do not know anyone. If there is just one, this is the
answer. If there are more than one, no solution. :) Wonder if this is what
they want.
int res = -1;
for (int i=0; i < people.size(); i++)
{
if (!knowSomeone(people[i])) //should be O(1) here.
{
//2 person cases, no solution
if (res >= 0)
return -1;
else
res = i;
}
}
return res;

j*r2014-05-07 07:05

32 楼

Search for "Universal sink".
This is also an exercise question in Cormen's book (but in a different
disguise).

【在 b*****w 的大作中提到】

u*r2014-05-07 07:05

33 楼

我理解是图的结构没有建立好，所以没法在O(1)时间检查节点的出度。前面有人说的比
较清楚，你的基本操作只能是询问x是否认识y，如果要求x的出度，必须询问x是否认识
剩下的所有人，O(n)复杂度。
如果每个节点的出度跟入度都知道了，这题也太没技术含量了吧。

the
what

【在 t********e 的大作中提到】

: Since there is just one guy do not know anybody. Just go through everyone,
: count number of people do not know anyone. If there is just one, this is the
: answer. If there are more than one, no solution. :) Wonder if this is what
: they want.
: int res = -1;
: for (int i=0; i < people.size(); i++)
: {
: if (!knowSomeone(people[i])) //should be O(1) here.
: {
: //2 person cases, no solution

z*h2014-05-07 07:05

34 楼

定义了如下数据结构。是不是太繁琐了？
class Peolple
{
int ID;
ArrayList peopleIKnow;
public void People (int i)
{
ID = i;
}
public void addAcquaintance(People p)
...
}
public People findCelebrity(ArrayList people)
{
...
}

m*a2014-05-07 07:05

35 楼

google "find the sink in a directed graph"

r*k2014-05-07 07:05

36 楼

假设不知道是否一定有“名人”存在的情况下，至少需要多少复杂度的询问次数才能确
定是否有“名人”存在？不需要确定名人是谁。

m*g2014-05-07 07:05

37 楼

这里有O(n)的解法：
http://stackoverflow.com/questions/8704829/find-the-best-elemen

w*s2014-05-07 07:05

38 楼

hashmap?
suppose e(i,j) means i knows j;
for every edges in set E: e(i,j)
map1[j]++, map2[i]++
finally, iterate the map1, find the one who has n; for this one, check map2
that its value is 0 (doesn't know anyone else)

j*u2014-05-07 07:05

39 楼

淘汰法有道理，但是
如果X,Y互相不认识，X,Y都无法排除，因为
他们认识其他人，只是彼此不认识

a*m2014-05-07 07:05

40 楼

不对。
"ask 1"你需要扫描，这个扫描不是o(1)

【在 k***i 的大作中提到】

: 我想这个方法可以在O(n)内识别出来。

a*m2014-05-07 07:05

41 楼

询问的话可以直接问每个人，“你认识任何一个人不?”,如果题目没问题应该只有一个
回答否的。

【在 l*********8 的大作中提到】

p*22014-05-07 07:05

42 楼

X,Y互不认识可以全部被淘汰了。

【在 j***u 的大作中提到】

: 淘汰法有道理，但是
: 如果X,Y互相不认识，X,Y都无法排除，因为
: 他们认识其他人，只是彼此不认识

j*u2014-05-07 07:05

43 楼

谢谢提醒，你是对的，我遗漏了一步
那情况就全了:
1> X,Y 互相认识，都淘汰, 因为celebrity 不认识其他人，所以X,Y不是celebrity
2> X,Y互相不认识，说明X,Y中没有celebrity, 因为如果有的话，X肯定认识Y或Y肯定
认识X
3> X认识Y, Y不认识X 淘汰Y
4> Y认识X, X不认识Y, 淘汰X
那么可以2种方式
1>所有点(或矩阵编号）入stack, 每次弹出2个比较，要么淘汰2个，要么淘汰1个压回1
个，最后一定剩1个
2>其实也可以直接用一维数组保存，移动index的方式.
最后那个就是名人. 时间O(N)

【在 p*****2 的大作中提到】

:
: X,Y互不认识可以全部被淘汰了。

j*u2014-05-07 07:05

44 楼

刚才写错了，修改一下
3> X认识Y, Y不认识X 淘汰X
4> Y认识X, X不认识Y, 淘汰Y

回1

【在 j***u 的大作中提到】

:
: 谢谢提醒，你是对的，我遗漏了一步
: 那情况就全了:
: 1> X,Y 互相认识，都淘汰, 因为celebrity 不认识其他人，所以X,Y不是celebrity
: 2> X,Y互相不认识，说明X,Y中没有celebrity, 因为如果有的话，X肯定认识Y或Y肯定
: 认识X
: 3> X认识Y, Y不认识X 淘汰Y
: 4> Y认识X, X不认识Y, 淘汰X
: 那么可以2种方式
: 1>所有点(或矩阵编号）入stack, 每次弹出2个比较，要么淘汰2个，要么淘汰1个压回1