class Solution {
public:
int findJudge(int n, vector<vector<int>>& trust) {
}
};
997. 找到小镇的法官
小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。
如果小镇法官真的存在，那么：
给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。
如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -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
提示：
1 <= n <= 10000 <= trust.length <= 104trust[i].length == 2trust 中的所有trust[i] = [ai, bi] 互不相同ai != bi1 <= ai, bi <= n相似题目
原站题解
cpp 解法, 执行用时: 125 ms, 内存消耗: 63.2 MB, 提交时间: 2024-09-22 15:26:25
class Solution {
public:
int findJudge(int n, vector<vector<int>>& trust) {
vector<int> inDegrees(n + 1);
vector<int> outDegrees(n + 1);
for (auto& edge : trust) {
int x = edge[0], y = edge[1];
++inDegrees[y];
++outDegrees[x];
}
for (int i = 1; i <= n; ++i) {
if (inDegrees[i] == n - 1 && outDegrees[i] == 0) {
return i;
}
}
return -1;
}
};
javascript 解法, 执行用时: 80 ms, 内存消耗: 57.3 MB, 提交时间: 2024-09-22 15:26:07
/**
* @param {number} n
* @param {number[][]} trust
* @return {number}
*/
var findJudge = function(n, trust) {
const inDegrees = new Array(n + 1).fill(0);
const outDegrees = new Array(n + 1).fill(0);
for (const edge of trust) {
const x = edge[0], y = edge[1];
++inDegrees[y];
++outDegrees[x];
}
for (let i = 1; i <= n; ++i) {
if (inDegrees[i] === n - 1 && outDegrees[i] === 0) {
return i;
}
}
return -1;
};
java 解法, 执行用时: 2 ms, 内存消耗: 52.4 MB, 提交时间: 2024-09-22 15:25:42
class Solution {
public int findJudge(int n, int[][] trust) {
int[] inDegrees = new int[n + 1];
int[] outDegrees = new int[n + 1];
for (int[] edge : trust) {
int x = edge[0], y = edge[1];
++inDegrees[y];
++outDegrees[x];
}
for (int i = 1; i <= n; ++i) {
if (inDegrees[i] == n - 1 && outDegrees[i] == 0) {
return i;
}
}
return -1;
}
}
python3 解法, 执行用时: 87 ms, 内存消耗: 19.7 MB, 提交时间: 2024-09-22 15:25:28
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
inDegrees = Counter(y for _, y in trust)
outDegrees = Counter(x for x, _ in trust)
return next((i for i in range(1, n + 1) if inDegrees[i] == n - 1 and outDegrees[i] == 0), -1)
golang 解法, 执行用时: 124 ms, 内存消耗: 7.6 MB, 提交时间: 2021-06-17 18:28:09
func findJudge(n int, trust [][]int) int {
degree := make([][]int, n)
for i, _ := range degree {
degree[i] = []int{0, 0}
}
for _, item := range trust {
degree[item[0]-1][0]++ // 入度
degree[item[1]-1][1]++ // 出度
}
for i, d := range degree {
if d[0] == 0 && d[1] == n - 1 {
return i + 1
}
}
return -1
}