J*****v 发帖数: 314 | 1 Consider an X x Y array of 1's and 0s. The X axis represents "influences"
meaning that X influences Y. So, for example, if $array[3,7] is 1 that means
that 3 influences 7.
An "influencer" is someone who influences every other person, but is not
influenced by any other member.
Given such an array, write a function to determine whether or not an
"influencer" exists in the array.
https://www.glassdoor.com/Interview/Consider-an-X-x-Y-array-of-1-s-and-0s-
The-X-axis-represents-influences-meaning-that-X-influences-Y-So-for-example-
i-QTN_498161.htm |
J*****v 发帖数: 314 | 2 public boolean checkInfluencer(boolean[][] followingMatrix) {
if (followingMatrix == null || followingMatrix.length == 0 ||
followingMatrix[0].length == 0)
return false;
int len = followingMatrix.length;
int res = 0;
for (int i = 1; i < len; ++i) {
if (!followingMatrix[i][res] || followingMatrix[res][i]) {
res = i;
}
}
// verify it is indeed an influencer
for (int i = 0; i < len; i++) {
if (i == res) {
continue;
}
if (!followingMatrix[i][res] || followingMatrix[res][i]) {
return false;
}
}
return true;
} |
J*****v 发帖数: 314 | 3 public boolean hasInfluencer(int[][] followingMatrix) {
if (followingMatrix == null || followingMatrix.length == 0 ||
followingMatrix[0].length == 0)
return false;
int len = followingMatrix.length;
int res = 0;
for (int i = 1; i < len; ++i) {
if (followingMatrix[i][res] == 0 || followingMatrix[res][i] == 1
) {
res = i;
}
}
// verify it is indeed an influencer
for (int i = 0; i < len; i++) {
if (i == res) {
continue;
}
if (followingMatrix[i][res] == 0 || followingMatrix[res][i] == 1
) {
return false;
}
}
return true;
} |
o****o 发帖数: 35 | |
J*****v 发帖数: 314 | 5 是变种,但leetcode上说最多有一个名人,linkedin这道题有0个或多个influencers都
有可能。
【在 o****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这不是lc celebrity 的变种吗?
|
k******a 发帖数: 44 | 6 influence应该是有传递关系的吧?否则,x,y轴各扫一遍就行了。
有传递关系的话,那就y轴扫描一次,找到没有被influnced的点,如果有多于1个点,
那么就没有influencer
如果只有1个点,然后从这点开始做bfs, 看是否cover所有的点。
复杂度应该是(X*Y)级别 |
k******a 发帖数: 44 | 7
如果有多个,那就违背了
An "influencer" is someone who influences every other person, but is not
influenced by any other member.
【在 J*****v 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是变种,但leetcode上说最多有一个名人,linkedin这道题有0个或多个influencers都 : 有可能。
|
J*****v 发帖数: 314 | 8 还是你观察仔细,那就是和leetcode用同样的解法
【在 k******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 如果有多个,那就违背了 : An "influencer" is someone who influences every other person, but is not : influenced by any other member.
|
j********g 发帖数: 61 | 9 我觉得不用DFS。
你可以记录每一个candidate的 indegree,最后看谁的indegree是0,谁就是“
influencer”。这样的话时间复杂度是O(n^2),空间复杂度是O(n)。 |
s**********g 发帖数: 14942 | 10 celebrity解法是O(n)时间 O(1)空间
【在 j********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得不用DFS。 : 你可以记录每一个candidate的 indegree,最后看谁的indegree是0,谁就是“ : influencer”。这样的话时间复杂度是O(n^2),空间复杂度是O(n)。
|
c********t 发帖数: 5706 | 11 同意, 楼主贴的code有多余的check, 试试去掉
【在 s**********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : celebrity解法是O(n)时间 O(1)空间
|
J*****v 发帖数: 314 | 12 我这已经是O(N) time, O(1) space了,要去只能去一个followingMatrix[res][i] ==
1
你确定要去掉吗?
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 同意, 楼主贴的code有多余的check, 试试去掉
|
w***u 发帖数: 156 | 13 code里的followingMatrix含义到底是什么?
如果说 下面的statement 是正确的话
if $array[3,7] is 1 that means
that 3 influences 7.
那么条件应该改成.
if (followingMatrix[i][res] == 1 || followingMatrix[res][i] == 0 |
c********t 发帖数: 5706 | 14 同意
LZ Time O(n) Space O(1)没问题。 第一个循环只用 if (followingMatrix[i][res] =
= 1) 即可, 第二个循环有一部分第一个循环已经check了,不需要再做。
【在 w***u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : code里的followingMatrix含义到底是什么? : 如果说 下面的statement 是正确的话 : if $array[3,7] is 1 that means : that 3 influences 7. : 那么条件应该改成. : if (followingMatrix[i][res] == 1 || followingMatrix[res][i] == 0
|