P即将发布m43新机G3， FT5级乳摸# PhotoGear - 摄影器材
A*o
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;
}
http://www.mitbbs.com/article_t/JobHunting/32578885.html
http://tinyurl.com/lclxeez
感觉glassdoor上的解是有错误的,可以找到反例,自己改了一个出来,求拍砖,求讨论,谢
谢!
关键在于: 如果我改的解是对的, 为啥复杂度可以是O(n)的? 求指点
bool existInfluencer(vector
int n = v.size();
int i, j, k;
vector
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;
}
