读完本文,能够去力扣解决如下题目:
277.搜寻名人(Medium)
明天来探讨经典的「名流问题」:
给你n
集体的社交关系(你晓得任意两个人之间是否意识),而后请你找出这些人中的「名人」。
所谓「名人」有两个条件:
1、所有其他人都意识「名人」。
2、「名人」不意识任何其他人。
这是一个图相干的算法问题,社交关系嘛,实质上就能够形象成一幅图。
如果把每个人看做图中的节点,「意识」这种关系看做是节点之间的有向边,那么名人就是这幅图中一个非凡的节点:
这个节点没有一条指向其余节点的有向边;且其余所有节点都有一条指向这个节点的有向边。
或者说的业余一点,名人节点的出度为 0,入度为n - 1
。
那么,这n
集体的社交关系是如何示意的呢?
前文 图论算法根底 说过,图有两种存储模式,一种是邻接表,一种是邻接矩阵,邻接表的次要劣势是节约存储空间;邻接矩阵的次要劣势是能够迅速判断两个节点是否相邻。
对于名人问题,显然会常常须要判断两个人之间是否意识,也就是两个节点是否相邻,所以咱们能够用邻接表来示意人和人之间的社交关系。
那么,把名流问题形容成算法的模式就是这样的:
给你输出一个大小为n x n
的二维数组(邻接矩阵)graph
示意一幅有n
个节点的图,每个人都是图中的一个节点,编号为0
到n - 1
。
如果graph[i][j] == 1
代表第i
集体意识第j
集体,如果graph[i][j] == 0
代表第i
集体不意识第j
集体。
有了这幅图示意人与人之间的关系,请你计算,这n
集体中,是否存在「名人」?
如果存在,算法返回这个名人的编号,如果不存在,算法返回 -1。
函数签名如下:
int findCelebrity(int[][] graph);
比方输出的领接矩阵长这样:
那么算法应该返回 2,节点 2 合乎名人的个性。
力扣第 277 题「搜查名人」就是这个经典问题,不过并不是间接把邻接矩阵传给你,而是只通知你总人数n
,同时提供一个 APIknows
来查问人和人之间的社交关系:
// 能够间接调用,可能返回 i 是否意识 j
boolean knows(int i, int j);
// 请你实现:返回「名人」的编号
int findCelebrity(int n) {
// todo
}
很显著,knows
API 实质上还是在拜访邻接矩阵。为了简略起见,咱们前面就按力扣的题目模式来探讨一下这个经典问题。
暴力解法
咱们拍拍脑袋就能写出一个简略粗犷的算法:
int findCelebrity(int n) {
for (int cand = 0; cand < n; cand++) {
int other;
for (other = 0; other < n; other++) {
if (cand == other) continue;
// 保障其他人都意识 cand,且 cand 不意识任何其他人
// 否则 cand 就不可能是名人
if (knows(cand, other) || !knows(other, cand)) {
break;
}
}
if (other == n) {
// 找到名人
return cand;
}
}
// 没有一个人合乎名人个性
return -1;
}
cand
是候选人(candidate)的缩写,咱们的暴力算法就是从头开始穷举,把每个人都视为候选人,判断是否合乎「名人」的条件。
方才也说了,knows
函数底层就是在拜访一个二维的邻接矩阵,一次调用的工夫复杂度是 O(1),所以这个暴力解法整体的最坏工夫复杂度是 O(N^2)。
那么,是否有其余高超的方法来优化工夫复杂度呢?其实是有优化空间的,你想想,咱们当初最耗时的中央在哪里?
对于每一个候选人cand
,咱们都要用一个内层 for 循环去判断这个cand
到底符不合乎「名人」的条件。
这个内层 for 循环看起来就蠢,尽管判断一个人「是名人」必须用一个 for 循环,但判断一个人「不是名人」就不必这么麻烦了。
因为「名人」的定义保障了「名人」的唯一性,所以咱们能够利用排除法,先排除那些显然不是「名人」的人,从而防止 for 循环的嵌套,升高工夫复杂度。
优化解法
我再反复一遍所谓「名人」的定义:
1、所有其他人都意识名人。
2、名人不意识任何其他人。
这个定义就很有意思,它保障了人群中最多有一个名人。
这很好了解,如果有两个人同时是名人,那么这两条定义就自圆其说了。
换句话说,只有察看任意两个候选人的关系,我肯定能确定其中的一个人不是名人,把他排除。
至于另一个候选人是不是名人,只看两个人的关系必定是不能确定的,但这不重要,重要的是排除掉一个必然不是名人的候选人,放大了包围圈。
这是优化的外围,也是比拟难了解的,所以咱们先来说说为什么察看任意两个候选人的关系,就能排除掉一个。
你想想,两个人之间的关系可能是什么样的?
无非就是四种:你意识我我不意识你,我意识你你不意识我,咱俩相互意识,咱两相互不意识。
如果把人比作节点,红色的有向边示意不意识,绿色的有向边示意意识,那么两个人的关系无非是如下四种状况:
无妨认为这两个人的编号别离是cand
和other
,而后咱们逐个剖析每种状况,看看怎么排除掉一个人。
对于状况一,cand
意识other
,所以cand
必定不是名人,排除。因为名人不可能意识他人。
对于状况二,other
意识cand
,所以other
必定不是名人,排除。
对于状况三,他俩相互意识,必定都不是名人,能够轻易排除一个。
对于状况四,他俩互不意识,必定都不是名人,能够轻易排除一个。因为名人应该被所有其他人意识。
综上,只有察看任意两个之间的关系,就至多能确定一个人不是名人,上述情况判断能够用如下代码示意:
if (knows(cand, other) || !knows(other, cand)) {
// cand 不可能是名人
} else {
// other 不可能是名人
}
如果可能了解这一个特点,那么写出优化解法就简略了。
咱们能够一直从候选人当选两个进去,而后排除掉一个,直到最初只剩下一个候选人,这时候再应用一个 for 循环判断这个候选人是否是货真价实的「名人」。
这个思路的残缺代码如下:
int findCelebrity(int n) {
if (n == 1) return 0;
// 将所有候选人装进队列
LinkedList<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
q.addLast(i);
}
// 始终排除,直到只剩下一个候选人进行循环
while (q.size() >= 2) {
// 每次取出两个候选人,排除一个
int cand = q.removeFirst();
int other = q.removeFirst();
if (knows(cand, other) || !knows(other, cand)) {
// cand 不可能是名人,排除,让 other 离队
q.addFirst(other);
} else {
// other 不可能是名人,排除,让 cand 离队
q.addFirst(cand);
}
}
// 当初排除得只剩一个候选人,判断他是否真的是名人
int cand = q.removeFirst();
for (int other = 0; other < n; other++) {
if (other == cand) {
continue;
}
// 保障其他人都意识 cand,且 cand 不意识任何其他人
if (!knows(other, cand) || knows(cand, other)) {
return -1;
}
}
// cand 是名人
return cand;
}
这个算法防止了嵌套 for 循环,工夫复杂度降为 O(N) 了,不过引入了一个队列来存储候选人汇合,应用了 O(N) 的空间复杂度。
PS:LinkedList
的作用只是充当一个容器把候选人装起来,每次找出两个进行比拟和淘汰,但至于具体找出哪两个,都是无所谓的,也就是说候选人离队的程序无所谓,咱们用的是addFirst
只是不便后续的优化,你齐全能够用addLast
,后果都是一样的。
是否能够进一步优化,把空间复杂度也优化掉?
最终解法
如果你可能了解下面的优化解法,其实能够不须要额定的空间解决这个问题,代码如下:
int findCelebrity(int n) {
// 先假如 cand 是名人
int cand = 0;
for (int other = 1; other < n; other++) {
if (!knows(other, cand) || knows(cand, other)) {
// cand 不可能是名人,排除
// 假如 other 是名人
cand = other;
} else {
// other 不可能是名人,排除
// 什么都不必做,持续假如 cand 是名人
}
}
// 当初的 cand 是排除的最初后果,但不能保障肯定是名人
for (int other = 0; other < n; other++) {
if (cand == other) continue;
// 须要保障其他人都意识 cand,且 cand 不意识任何其他人
if (!knows(other, cand) || knows(cand, other)) {
return -1;
}
}
return cand;
}
咱们之前的解法用到了LinkedList
充当一个队列,用于存储候选人汇合,而这个优化解法利用other
和cand
的交替变动,模仿了咱们之前操作队列的过程,防止了应用额定的存储空间。
当初,解决名人问题的解法工夫复杂度为 O(N),空间复杂度为 O(1),曾经是最优解法了。
最初说个福利,今天 6:00 前在京东自营购买《labuladong 的算法小抄》有折扣,7.7 折叠加满 100-50 或者单本 6 折,有趣味的读者不要错过哦:
查看更多优质算法文章 点击这里,手把手带你刷力扣,致力于把算法讲清楚!我的 算法教程 曾经取得 90k star,欢送点赞!