w********0
发帖数: 377 | 1 给一群人，从里面找出来谁也不认识他，他也不认识任何人的那些人。
假设我们有bool knows(a,b) //1:互相认识， 0，互不认识
就相当于在一个无向图里，找出那些跟其他点都不相连的孤立点。
最暴力地方法O（n*n）， 每个人都问他人不认识其所有人。
有没有什么更快的方法呀？ 谢谢。 |
e********2
发帖数: 495 | 2 leetcode
【在 w********0 的大作中提到】
: 给一群人，从里面找出来谁也不认识他，他也不认识任何人的那些人。
: 假设我们有bool knows(a,b) //1:互相认识， 0，互不认识
: 就相当于在一个无向图里，找出那些跟其他点都不相连的孤立点。
: 最暴力地方法O（n*n）， 每个人都问他人不认识其所有人。
: 有没有什么更快的方法呀？ 谢谢。
|
C****6
发帖数: 24 | |
w********0
发帖数: 377 | 4 但是不太一样。这个认识是没有方向的，只要求互相认识，就是如果A认识b， b就认识
A。
相当于无向边。而且要找出那些孤立的点。
【在 C****6 的大作中提到】
: https://leetcode.com/problems/find-the-celebrity/
|
t**r
发帖数: 3428 | 5 2 run can solve this problem.
O(n)
use 2 set you can. |
w********0
发帖数: 377 | 6 不太明白。可以所得在具体一点吗？ 这道题没有告诉你有多少个孤立的点，有可能一
个没有，也有可能n个全是孤立点。我怎么觉得要是n个全是孤立点， 你必须要n*n呀。
不全部问一遍，不可能知道呀。
【在 t**r 的大作中提到】
: 2 run can solve this problem.
: O(n)
: use 2 set you can.
|
w***n
发帖数: 58 | |
b********6
发帖数: 35437 | 8 总的原则就是遍历两遍，第一遍把所有有关联的点都会总到一起，放在一个set里或者
disjoint set，O(n log n)，不知道用hash table可不可以降为O(n). 第二遍把所有点
遍历，看这个点有没有出现在之前弄好的set里。set的查找是O( n log n), disjoint
set的查找是O(n), hash table的查找是O(n) |
w********0
发帖数: 377 | 9 可是 假设所有人互不认识 不可能通过nlgn 把所有的有关联的点汇总一起吧？ 必须n2
才能知道所有连接情况呀。不明白。
disjoint
【在 b********6 的大作中提到】
: 总的原则就是遍历两遍，第一遍把所有有关联的点都会总到一起，放在一个set里或者
: disjoint set，O(n log n)，不知道用hash table可不可以降为O(n). 第二遍把所有点
: 遍历，看这个点有没有出现在之前弄好的set里。set的查找是O( n log n), disjoint
: set的查找是O(n), hash table的查找是O(n)
|
B********4
发帖数: 7156 | 10 你说的是最坏情况为n^2. 他这个是平均情况。
根据他的思路，我改良一下。对某个人查找，一旦找到他有一个朋友就不用继续找了，
把他和他的朋友都删掉。这样剩下的必然是没有朋友的孤家寡人。这个算法应该是比n^
2强，但我无法证明是nlogn。
n2才能知道所有连接情况呀。不明白。
【在 w********0 的大作中提到】
: 可是 假设所有人互不认识 不可能通过nlgn 把所有的有关联的点汇总一起吧？ 必须n2
: 才能知道所有连接情况呀。不明白。
:
: disjoint
|
|
|
w********0
发帖数: 377 | 11 对 我也觉得这个提的最坏情况应该是n2，就是谁都不认识谁。但是你不能删掉有朋友
的人呀。万一剩下的人里面有认识你删的人的情况呢？
n^
【在 B********4 的大作中提到】
: 你说的是最坏情况为n^2. 他这个是平均情况。
: 根据他的思路，我改良一下。对某个人查找，一旦找到他有一个朋友就不用继续找了，
: 把他和他的朋友都删掉。这样剩下的必然是没有朋友的孤家寡人。这个算法应该是比n^
: 2强，但我无法证明是nlogn。
:
: n2才能知道所有连接情况呀。不明白。
|
r*******g
发帖数: 1335 | 12 union find, n*lgn可以解决问题，第一遍给出所有的集合的parent id，第二遍就简单
了。 |
B********4
发帖数: 7156 | 13 你说的对，不能删掉有朋友的人。
友的人呀。万一剩下的人里面有认识你删的人的情况呢？
【在 w********0 的大作中提到】
: 对 我也觉得这个提的最坏情况应该是n2，就是谁都不认识谁。但是你不能删掉有朋友
: 的人呀。万一剩下的人里面有认识你删的人的情况呢？
:
: n^
|
w********0
发帖数: 377 | 14 我感觉能做的就是比过的 就不再比了。但是worse case还是n2。而且我也分析不出来
时间复杂度
【在 B********4 的大作中提到】
: 你说的对，不能删掉有朋友的人。
:
: 友的人呀。万一剩下的人里面有认识你删的人的情况呢？
|
w********0
发帖数: 377 | 15 ，第一遍给出所有的集合的parent id O(nlgn)如何做到？
【在 r*******g 的大作中提到】
: union find, n*lgn可以解决问题，第一遍给出所有的集合的parent id，第二遍就简单
: 了。
|
r*******g
发帖数: 1335 | 16 union find不就是做这个事情的吗
https://leetcode.com/problems/number-of-islands-ii/
上面是leetcode上的一道题，也是union find做的。
所以一遍就得到所有节点的parent，当然worst case不是nlgn。
然后，只需要再次遍历，看看哪些parent id是只有自己的。
【在 w********0 的大作中提到】
: ，第一遍给出所有的集合的parent id O(nlgn)如何做到？
|
p**r
发帖数: 5853 | 17 keyword:无向
【在 r*******g 的大作中提到】
: union find不就是做这个事情的吗
: https://leetcode.com/problems/number-of-islands-ii/
: 上面是leetcode上的一道题，也是union find做的。
: 所以一遍就得到所有节点的parent，当然worst case不是nlgn。
: 然后，只需要再次遍历，看看哪些parent id是只有自己的。
|
b********6
发帖数: 35437 | 18 你的初始条件里连接信息总要存在什么地方吧，先只读那些连接信息，把所有参与的点
全部会总到一起就行了。为了方便第二遍的遍历，需要搞成tree或者hash table的结构
，所以第一步会总需要n log n
n2
【在 w********0 的大作中提到】
: 可是 假设所有人互不认识 不可能通过nlgn 把所有的有关联的点汇总一起吧？ 必须n2
: 才能知道所有连接情况呀。不明白。
:
: disjoint
|
r*******g
发帖数: 1335 | 19 Oh
这道题已知条件只是一个bool function，所以好像没有什么算法，就是每个节点遍历。
【在 p**r 的大作中提到】
: keyword:无向
|
g******d
发帖数: 152 | 20 O(N)
linkedin就拿这个考过我。给了提示才会的。
假设存在N＊N的matrix里面。走第一行，发现有他认识的人，拿这一列以后都不用看了 |
|
|
g******d
发帖数: 152 | |
x****y
发帖数: 252 | 22 你过了拿到他家offer？
【在 g******d 的大作中提到】
: O(N)
: linkedin就拿这个考过我。给了提示才会的。
: 假设存在N＊N的matrix里面。走第一行，发现有他认识的人，拿这一列以后都不用看了
|
g******d
发帖数: 152 | 23
【在 x****y 的大作中提到】
: 你过了拿到他家offer？
|
