[997].找到小镇法官
程序员文章站
2022-05-21 15:06:04
...
找到小镇法官
文章目录
题目
在一个小镇里,按从 1
到 N
标记了 N
个人。
传言称,这些人中有一个是小镇上的秘密法官。
如果小镇的法官真的存在,那么:
- 小镇的法官不相信任何人。
- 每个人(除了小镇法官外)都信任小镇的法官。
- 只有一个人同时满足属性 1 和属性 2 。
给定数组 trust
,该数组由信任对 trust[i] = [a, b]
组成,表示标记为 a
的人信任标记为 b
的人。
如果小镇存在秘密法官并且可以确定他的身份,请返回该法官的标记。否则,返回 -1
。
示例 1:
输入:N = 2, trust = [[1,2]]
输出:2
示例 2:
输入:N = 3, trust = [[1,3],[2,3]]
输出:3
示例 3:
输入:N = 3, trust = [[1,3],[2,3],[3,1]]
输出:-1
示例 4:
输入:N = 3, trust = [[1,2],[2,3]]
输出:-1
示例 5:
输入:N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
输出:3
函数原型
C的函数原型:
int findJudge(int N, int** trust, int trustSize, int* trustColSize){}
- 代表有 个人
- 是一个二维数组,记录顶点之间的关系
- 是 的长度,
-
,这是什么东东。
边界判断
经过测试,有一种特殊情况。
N=1, trust = []
单独做一次判断:
int findJudge(int N, int** trust, int trustSize, int* trustColSize){
if(trust == NULL)
return N;
}
算法设计:图论问题->度数
看成有向图,判断每个点的出度与入度的情况即可~
- 法官不相信任何人,说明法官出度为
- 所有人都信任法官,说明法官的入度为
int findJudge(int N, int** trust, int trustSize, int* trustColSize){
if(trust == NULL)
return N;
int in_degree[1024] = {0}; // 开辟一个数组,记录每个点的入度(被信任了)
int out_degree[1024] = {0}; // 开辟一个数组,记录每个点的出度(信任别人)
for(int i=0; i<trustSize; i++){
out_degree[trust[i][0]]++; // a 信任 b,第一个元素即a,a的出度+1
in_degree[trust[i][1]]++; // a 信任 b,第二个元素即b,b的入度+1
}
for(int i=1; i<=N; i++)
if( out_degree[i] == 0 && in_degree[i] == N-1 ) // 如果有一个人被信任了N-1次,且不信任任何人,他就是法官,返回其编号
return i;
return -1;
}
- 法官不相信任何人,说明法官出度为
- 所有人都信任法官,说明法官的入度为
- 所有人的度数相加,法官的入度 + 出度 =
可优化,用一个数组记录最关键的入度即可。
int findJudge(int N, int** trust, int trustSize, int* trustColSize){
if(trust == NULL)
return N;
int in_degree[1024] = {0}; // 开辟一个数组,记录每个点的入度(被信任了)
for(int i=0; i<trustSize; i++){
in_degree[trust[i][0]]--; // a 信任 b,第一个元素即a,a的入度-1(法官是不可能在第一个位置的,所以为0,N-1+0 = N-1)
in_degree[trust[i][1]]++; // a 信任 b,第二个元素即b,b的入度+1
}
for(int i=1; i<=N; i++)
if( in_degree[i] == N-1 ) // 如果有一个人被信任了N-1次,且不信任任何人,他就是法官,返回其编号
return i;
return -1;
}
度数算法复杂度:
- 时间复杂度:
- 空间复杂度:
上一篇: 蓝桥杯 第八届蓝桥杯Java语言B组