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 的大作中提到】
: 这不是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 的大作中提到】
: 是变种，但leetcode上说最多有一个名人，linkedin这道题有0个或多个influencers都
: 有可能。
|
J*****v
发帖数: 314 | 8 还是你观察仔细，那就是和leetcode用同样的解法
【在 k******a 的大作中提到】
:
: 如果有多个，那就违背了
: 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 的大作中提到】
: 我觉得不用DFS。
: 你可以记录每一个candidate的 indegree，最后看谁的indegree是0，谁就是“
: influencer”。这样的话时间复杂度是O(n^2)，空间复杂度是O(n）。
|
c********t
发帖数: 5706 | 11 同意， 楼主贴的code有多余的check, 试试去掉
【在 s**********g 的大作中提到】
: celebrity解法是O(n)时间 O(1)空间
|
J*****v
发帖数: 314 | 12 我这已经是O(N) time, O(1) space了，要去只能去一个followingMatrix[res][i] ==
1
你确定要去掉吗？
【在 c********t 的大作中提到】
: 同意， 楼主贴的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 的大作中提到】
: code里的followingMatrix含义到底是什么?
: 如果说 下面的statement 是正确的话
: if $array[3,7] is 1 that means
: that 3 influences 7.
: 那么条件应该改成.
: if (followingMatrix[i][res] == 1 || followingMatrix[res][i] == 0
|
