S**I
发帖数: 15689 | 1 ☆─────────────────────────────────────☆
bailngw (bailing) 于 (Tue Apr 10 12:32:15 2012, 美东) 提到:
昨天居然又被问到了：
屋子里有n个人，如果i 认识 j, 那么他们之间有条directed edge. 如果有这么一个人
：大家都认识他，但他不认识其他任何人，我们叫他celebrity.
如果在O(n)时间找出celebrity?
谢谢
☆─────────────────────────────────────☆
longway2008 (longway2008) 于 (Tue Apr 10 12:39:51 2012, 美东) 提到:
DFS ?
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Apr 10 12:39:58 2012, 美东) 提到:
建个图之有入没有出就是了
昨天居然又被问到了：屋子里有n个人，如果i 认识 j, 那么他们之间有条directed
edge. 如果有这么一个人：大家都认识他，但他不认识其他任何人，我们叫他celebr..
......
★ Sent from iPhone App: iReader Mitbbs Lite 7.52
☆─────────────────────────────────────☆
longway2008 (longway2008) 于 (Tue Apr 10 12:42:51 2012, 美东) 提到:
How does the input data structure store the "directed edges"?
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Tue Apr 10 12:44:56 2012, 美东) 提到:
google
☆─────────────────────────────────────☆
longway2008 (longway2008) 于 (Tue Apr 10 12:50:40 2012, 美东) 提到:
问题描述： 在一个聚会上有 n 个人，其中有一个名人，大家都认识他，但他却不认识
所有其他人。现在请你只通过询问来宾 x 是不是认识来宾 y 的方式把这个名人找出来
。最多只能使用 O(n) 次询问。
☆─────────────────────────────────────☆
xiaojiya (xiaojiya) 于 (Tue Apr 10 12:55:31 2012, 美东) 提到:
不重复的问下去，一定会问到这个名人,
这个名人没有下一个,所以stop
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Apr 10 12:57:57 2012, 美东) 提到:
认识淘汰x不认识淘汰y
问题描述： 在一个聚会上有 n 个人，其中有一个名人，大家都认识他，但他却不认识
所有其他人。现在请你只通过询问来宾 x 是不是认识来宾 y 的方式把这个名人找出来
。最多只能使用........
★ Sent from iPhone App: iReader Mitbbs Lite 7.52
☆─────────────────────────────────────☆
chenpp (chenpp) 于 (Tue Apr 10 12:58:07 2012, 美东) 提到:
建图的worst case是O(n^2)吧
..
☆─────────────────────────────────────☆
chenpp (chenpp) 于 (Tue Apr 10 12:59:04 2012, 美东) 提到:
这样没法确定所有人都认识名人。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Apr 10 13:01:53 2012, 美东) 提到:
Assume 有一个吧
这样没法确定所有人都认识名人。
★ Sent from iPhone App: iReader Mitbbs Lite 7.52
☆─────────────────────────────────────☆
karni (我没有昵称) 于 (Tue Apr 10 13:02:55 2012, 美东) 提到:
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.
☆─────────────────────────────────────☆
ggtx (ggtx) 于 (Tue Apr 10 13:14:34 2012, 美东) 提到:
"他却不认识所有其他人。"
是指他不认识任何一个其他的人，还是他认识some of them?
☆─────────────────────────────────────☆
evaol (evaol) 于 (Tue Apr 10 13:15:35 2012, 美东) 提到:
即使不assume存在一个也可以O(n)找到答案。如果存在，只能有一个。
用上面的x,y淘汰法可以O(n)确定一个candidate，然后问其余n-1个人是不是认识这个
candidate，如果都认识，那就找到了名人。否则名人就不存在。
☆─────────────────────────────────────☆
egaisi (worrying) 于 (Tue Apr 10 13:16:29 2012, 美东) 提到:
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.
☆─────────────────────────────────────☆
demon (brute-force) 于 (Tue Apr 10 13:16:30 2012, 美东) 提到:
根据题目条件这个名人必然只有一个， 所以只需要找到唯一的一个人都不认识的人即
可。
但是这好像过于trivial了。
☆─────────────────────────────────────☆
karni (我没有昵称) 于 (Tue Apr 10 13:18:10 2012, 美东) 提到:
我想这个方法可以在O(n)内识别出来。
☆─────────────────────────────────────☆
demon (brute-force) 于 (Tue Apr 10 13:19:23 2012, 美东) 提到:
加上这个限制貌似题目更make sense一些。
☆─────────────────────────────────────☆
yishan (易山风雨易江秋) 于 (Tue Apr 10 13:26:11 2012, 美东) 提到:
妙法！
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Apr 10 13:28:35 2012, 美东) 提到:
是。
☆─────────────────────────────────────☆
chenpp (chenpp) 于 (Tue Apr 10 13:52:14 2012, 美东) 提到:
问其余n-1个人是不是认识这个candidate的复杂度，如果不用hash表的话，不是O(n)吧？
如果用hash表的话，建表的代价就是O(n^2)了。
☆─────────────────────────────────────☆
chenpp (chenpp) 于 (Tue Apr 10 13:55:15 2012, 美东) 提到:
关键问题是：
问A是否知道B的代价是O(1)么？
one
☆─────────────────────────────────────☆
evaol (evaol) 于 (Tue Apr 10 15:01:21 2012, 美东) 提到:
应该需要邻接矩阵。或者像后面那个描述，可以直接问x是否认识y，也就是O(1)。
☆─────────────────────────────────────☆
flyinocean12 (生无所求) 于 (Tue Apr 10 15:18:45 2012, 美东) 提到:
问x，认识y吗？如果认识，x肯定不是名人；如果不认识，y肯定不是名人。所以每次
ask必然淘汰一次，经过最多n次ask，肯定能找出名人。
问一次的代价应该是O（1）吧，要不N代表什么。。。
☆─────────────────────────────────────☆
zyy (无聊) 于 (Tue Apr 10 15:46:56 2012, 美东) 提到:
很简单的题，由此开始满十个包子我贴个答案
☆─────────────────────────────────────☆
cx3959 (skyblueX) 于 (Tue Apr 10 16:00:02 2012, 美东) 提到:
可以用对每个人用count，如果有人认识他就++，认识别人就--， 最后谁的count是n就
是那个人
☆─────────────────────────────────────☆
zyy (无聊) 于 (Tue Apr 10 16:20:53 2012, 美东) 提到:
你这个就是统计入度和出度，复杂度O(n*n)
还是给包子等答案吧
☆─────────────────────────────────────☆
utar (由它) 于 (Tue Apr 10 16:58:49 2012, 美东) 提到:
同意这个。每次淘汰一个人，问n－１次最后只能剩下一个。
柯南说得好，真相只有一个，排除所有不可能，剩下的就是答案。
☆─────────────────────────────────────☆
longway2008 (longway2008) 于 (Tue Apr 10 17:09:16 2012, 美东) 提到:
int FindCelibrity(bool ** know, int n)
{
if (know == NULL || n<1) return -1;
int cel=0;
for (int i=1; i
if (know[cel][i])
cel = i;
return cel;
}
☆─────────────────────────────────────☆
tradertobe (builder) 于 (Tue Apr 10 17:42:48 2012, 美东) 提到:
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;
☆─────────────────────────────────────☆
jenvor (jenvor) 于 (Tue Apr 10 17:43:09 2012, 美东) 提到:
Search for "Universal sink".
This is also an exercise question in Cormen's book (but in a different
disguise).
☆─────────────────────────────────────☆
utar (由它) 于 (Tue Apr 10 19:28:51 2012, 美东) 提到:
我理解是图的结构没有建立好，所以没法在O(1)时间检查节点的出度。前面有人说的比
较清楚，你的基本操作只能是询问x是否认识y，如果要求x的出度，必须询问x是否认识
剩下的所有人，O(n)复杂度。
如果每个节点的出度跟入度都知道了，这题也太没技术含量了吧。
the
what
☆─────────────────────────────────────☆
zhangh (zhuangzhuang) 于 (Tue Apr 10 19:41:50 2012, 美东) 提到:
定义了如下数据结构。是不是太繁琐了？
class Peolple
{
int ID;
ArrayList peopleIKnow;
public void People (int i)
{
ID = i;
}
public void addAcquaintance(People p)
...
}
public People findCelebrity(ArrayList people)
{
...
}
☆─────────────────────────────────────☆
mosesjoshua (mosesjoshua) 于 (Tue Apr 10 20:13:06 2012, 美东) 提到:
google "find the sink in a directed graph"
☆─────────────────────────────────────☆
robck (万廷) 于 (Tue Apr 10 20:20:43 2012, 美东) 提到:
假设不知道是否一定有“名人”存在的情况下，至少需要多少复杂度的询问次数才能确
定是否有“名人”存在？不需要确定名人是谁。
☆─────────────────────────────────────☆
myanything (Lanson) 于 (Wed Apr 11 03:57:44 2012, 美东) 提到:
这里有O(n)的解法：
http://stackoverflow.com/questions/8704829/find-the-best-elemen
☆─────────────────────────────────────☆
winetricks (winetricks) 于 (Wed Apr 11 11:02:46 2012, 美东) 提到:
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)
☆─────────────────────────────────────☆
jchau (jchau) 于 (Sun Apr 15 18:36:13 2012, 美东) 提到:
淘汰法有道理，但是
如果X,Y互相不认识，X,Y都无法排除，因为
他们认识其他人，只是彼此不认识
☆─────────────────────────────────────☆
autumnworm (虫子，秋天的) 于 (Mon Apr 16 02:31:16 2012, 美东) 提到:
不对。
"ask 1"你需要扫描，这个扫描不是o(1)
☆─────────────────────────────────────☆
autumnworm (虫子，秋天的) 于 (Mon Apr 16 02:33:41 2012, 美东) 提到:
询问的话可以直接问每个人，“你认识任何一个人不?”,如果题目没问题应该只有一个
回答否的。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Mon Apr 16 03:44:18 2012, 美东) 提到:
X,Y互不认识可以全部被淘汰了。
☆─────────────────────────────────────☆
jchau (jchau) 于 (Mon Apr 16 23:25:02 2012, 美东) 提到:
谢谢提醒，你是对的，我遗漏了一步
那情况就全了:
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)
☆─────────────────────────────────────☆
jchau (jchau) 于 (Mon Apr 16 23:28:52 2012, 美东) 提到:
刚才写错了，修改一下
3> X认识Y, Y不认识X 淘汰X
4> Y认识X, X不认识Y, 淘汰Y
回1 |
|
