A*****o
发帖数: 284 | 1 原帖在这里
http://www.mitbbs.com/article_t/JobHunting/32578885.html
http://tinyurl.com/lclxeez
感觉glassdoor上的解是有错误的,可以找到反例,自己改了一个出来,求拍砖,求讨论,谢
谢!
关键在于: 如果我改的解是对的, 为啥复杂度可以是O(n)的? 求指点
bool existInfluencer(vector > &v) {
int n = v.size();
int i, j, k;
vector not_influencer(n, false);
for (i = 0; i < n; i++) {
if (not_influencer[i]) {
continue;
}
for (j = i+1; j < n; j++) {
if (v[i][j] == 0) {
break;
}
not_influencer[j] = true;
}
if (j == n) {
for (j = i-1; j >= 0; j--) {
if (v[i][j] == 0) {
break;
}
not_influencer[j] = true;
}
if (j == -1) {
for (k = 0; k < i; k++) {
if (v[k][i] == 1) {
break;
}
not_influencer[k] = true;
}
if (k == i) {
for (k = i+1; k < n; k++) {
if (v[k][i] == 1) {
break;
}
not_influencer[k] = true;
}
if (k == n) {
return true;
}
}
}
}
not_influencer[i] = true;
}
return false;
} | n****e
发帖数: 678 | | a********9
发帖数: 129 | 3 是不是如这个帖子http://www.mitbbs.com/article_t1/JobHunting/32579011_0_2.html 所说，
假设我们先建好graph,判断a是否influence b 还是需要O(n)时间，所以最终算法时间
是O(n^2) | x*******8
发帖数: 145 | 4 算法复杂度最优是O(n)。 毎call 一次matrix[i][j]，如果是0，i被排除，如果是1，j
被排除，那么n-1次就可以排除所有人得到一个candidate，然后验证，算row的和是不
是n-1，以及col的和是不0，如果是就找到了。 | w********s
发帖数: 214 | 5 LS的说法貌似有点问题，如果是1,j当然可以被排除，但是如果是0,i怎么能够排除呢？
题目的意思是说只要可以影响到别人不被别人影响就算是influencer吧？
并不是影响所有人的意思。 | l*n
发帖数: 529 | 6 celebrity问题是说所有人都认识。不知道这个influencer是不是类似定义的。
【在 w********s 的大作中提到】
: LS的说法貌似有点问题，如果是1,j当然可以被排除，但是如果是0,i怎么能够排除呢？
: 题目的意思是说只要可以影响到别人不被别人影响就算是influencer吧？
: 并不是影响所有人的意思。
| w**t
发帖数: 893 | 7 because I needs to influence all others
【在 w********s 的大作中提到】
: LS的说法貌似有点问题，如果是1,j当然可以被排除，但是如果是0,i怎么能够排除呢？
: 题目的意思是说只要可以影响到别人不被别人影响就算是influencer吧？
: 并不是影响所有人的意思。
| b****f
发帖数: 138 | |
|
